数据漏洞
查看原帖
数据漏洞
324632
Skeleton_Huo楼主2024/10/10 18:02

似乎没有答案为二元环的数据,例如这份代码能通过,但

5
2 1 4 5 3

就能卡掉

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n;
vector<int> e[N];
bool vis[N];
vector<int> path;

void dfs(int u, int fa, bool &flag, int &cyc) {
	vis[u] = 1, path.emplace_back(u);
	for (auto v : e[u]) {
		if (vis[v]) {
			if (flag || v == fa) continue;
			flag = 1, cyc = 1;
			for (int i = path.size() - 1; path[i] != v; i--) cyc++;
			continue;
		}
		dfs(v, u, flag, cyc);
	}
	path.pop_back();
}

int main() {
	cin >> n;
	
	int ans = n;
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		e[i].emplace_back(t);
		e[t].emplace_back(i);
	}
	
	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		path.clear();
		bool flag = 0;
		int cyc = 0;
		dfs(i, 0, flag, cyc);
		ans = min(ans, cyc);
	}
	
	cout << ans;
	
	return 0;
}
2024/10/10 18:02
加载中...