拓扑排序学习

其实这个就是bfs的应用，但是值得注意的是，如果图中出现了单个的环

我们分析一下，入度为0的肯定不能选，其次他的所有监视的对象要选，可能出现单个环的情况，对于环，我们要选一半的人

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

int n;
const int N = (int)1e6+5;
int e[N],vis[N],du[N];
int choose[N];
int ans = 0;

void bfs(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(!du[i]) q.push(i);// 入度为0的都不选，因为没有人监督 
	}
	while(q.size()){
		int u = q.front(); q.pop();
		vis[u] = 1;
		if(choose[u]){
			// 如果这个点已经选了
			// 他监督的人的度要减一
			du[e[u]]--;
			if(!du[e[u]]) q.push(e[u]); 
		}else{
			// 如果没被选,那么他监督的人就一定要被选
			if(!choose[e[u]]){  // 要避免重复放 
				ans++; q.push(e[u]);
			}
			choose[e[u]] = 1; 
		}
	}
	// 开始找剩下的环
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			int cnt = 1;
			int to = e[i];
			vis[i] = 1;
			while(!vis[to]){
				vis[to] = 1; // 标记为1
				cnt++;
				to = e[to]; 
			}
			ans += cnt/2;
		}
	} 
}

int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> e[i];
		du[e[i]] ++; // 入度加一 
	}
	bfs();
	cout << ans;
	return 0;
}