建议加强数据
查看原帖
建议加强数据
906859
Adam1101楼主2024/10/12 16:09

只需枚举前 97 个同学并 dfs 求最小环即可通过,如这份代码:

#include <bits/stdc++.h>
using namespace std;

int f[200010];
int dfn[200010];
int cnt = 0;
int ans = INT_MAX;

void dfs(int x) {
	dfn[x] = ++cnt;
//	cout << cnt << " " << x << "\n";
	int y = f[x];
	if (dfn[y]) {
		ans = min(ans, dfn[x] - dfn[y] + 1);
		return ;
	}
	dfs(y);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> f[i];
	}
	for (int i = 1; i <= min(n, 97); i++) {
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			dfn[i] = 0;
		}
		dfs(i);
	}
	cout << ans << "\n";
	return 0;
}

提交记录

建议添加一组数据为多组三元环中靠后的位置添加一组二元环,类似于:

n
2 3 1 5 6 4 ... (i+1) i ... (n-1) n (n-2)
2024/10/12 16:09
加载中...