[POI 2004]SZP
Description
Byteotian 中央情报局 (BIA) 雇佣了许多特工. 他们每个人的工作就是监视另一名特工.Byteasar 国王需要进行一次秘密行动,所以他要挑选尽量多的信得过的特工. 但是这项任务是如此的机密以至于所有参加行动的特工都必须至少被另一名没有参加任务的特工所监视(就是说如果某个特工参加了行动,那么原先监视他的那些特工中至少要有一个没有参加进行动). 给出监视任务的详情,要求计算最多能有多少个特工参与其中.
Input
第一行只有一个整数, n – 特工的总数, 2 <= n <= 1000000. 特工从 1 到 n 编号. 接下来 n行每行一个整数 ak 表示特工 k 将要监视特工 ak , 1 <= k <= n, 1 <= ak <= n, ak <> k.
Output
打印一个数,最多能有多少特工参加入这个任务.
Sample Input
6
2
3
1
3
6
5
Sample Output
3
HINT
题解
可以用贪心+拓扑排序做。
首先我们可以发现，入度为0的点必然不能被选，我们先将所有点标记为不选，将入度为0的点加入队列中。
由贪心的思想，我们为了被选的点更多，我们要将不选的点所指向的点选上。
证明：若点i确定为不选，若ak[i]不选也只能提供一个点被选（ak[i]指向的点），故ak[i]选上不会差。
若所有指向i的点均选，则i只能是不选。
由于图可能不连通还可能有环。我们只需要最后剩下的环从任意处切开即可。
由于我们在拓扑排序的过程中在环上做过标记。我们只要考虑没做过标记的一段，即有i标记为不选，ak[i]标记也为不选，显然我们要标记ak[i]为选。
#include#include #include #include #include #include #include using namespace std;int n,m,ans;int gi(){ int ans=0,f=1;char i=getchar(); while(i<'0'||i>'9'){ if(i=='-')f=-1;i=getchar();} while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();} return ans*f;}struct node{ int next,to;}edge[1000005];int head[1000005],size=1,in[1000005],cnt[1000005],to[1000005];void putin(int from,int to){ size++; edge[size].next=head[from]; edge[size].to=to; head[from]=size;}void bfs(){ queue mem; int i,j; for(i=1;i<=n;i++) if(!in[i])mem.push(i); while(!mem.empty()) { int x=mem.front();mem.pop(); if(!cnt[x]) { for(i=head[x];i!=-1;i=edge[i].next) { int y=edge[i].to; if(in[y]) { cnt[y]++; in[y]--; if(!in[y])mem.push(y); } } } else { ans++; for(i=head[x];i!=-1;i=edge[i].next) { int y=edge[i].to; if(in[y]) { in[y]--; if(!in[y])mem.push(y); } } } }}void find(int r){ int i;in[r]=0; if(cnt[r])ans++; if(cnt[to[r]])ans++; if(!cnt[r]&&!cnt[to[r]]) { ans++; cnt[to[r]]++; } for(i=to[r];to[i]!=r;i=to[i]) { if(!cnt[i]&&!cnt[to[i]]) { ans++; cnt[to[i]]++; } else if(cnt[to[i]])ans++; in[i]=0; } in[i]=0;}int main(){ memset(head,-1,sizeof(head)); int i,j; n=gi(); for(i=1;i<=n;i++) { j=gi(); putin(i,j); to[i]=j; in[j]++; } bfs(); for(i=1;i<=n;i++) if(in[i])find(i); printf("%d",ans); return 0;}