蓝桥杯备考：拓扑排序+DFS（信息传递）

本题我们只要求环有多少元素就有多少回合游戏

 

我们可以用拓扑排序把环之外的元素打上标记，然后用遍历没打上标记的元素，统计环的元素个数，当然，我们可能不只有一个环，我们取得所有环的最小值就行了

#include <iostream>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
int ne[N];//存图 
int n;
int in[N];//存入度 
bool st[N];
int cnt;
void dfs(int x)
{cnt++;st[x] = true;int y = ne[x];if (!st[y] && y){dfs(y);}
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> ne[i];in[ne[i]]++;}queue<int> q;for (int i = 1; i <= n; i++){if (in[i] == 0) q.push(i);}while (q.size()){auto t = q.front(); q.pop();st[t] = true;in[ne[t]]--;if (in[ne[t]] == 0){q.push(ne[t]);}}int ret = n;for (int i = 1; i <= n; i++){cnt = 0;if (!st[i]){dfs(i);ret = min(ret, cnt);}}cout << ret << endl;return 0;
}