题目

https://jzoj.net/senior/#contest/show/2045/2

小结

这题，我们可以转化成一个图论问题，我们只需要记录入度个数就好了 首先， 然后我们把它删掉之后，就可以看到，它所能控制的点就合法了，因为它可以被一个不合法的点控制，并把合法的点的出度删掉。 每次就是这样做。 最后一种gg的情况，要特判一下。。。。 就是有环的情况： 于是，这样一题看似很难的题就被化成一个没有任何算法的题了。。。。

var i,j,n,m,k,tot,ans:longint; a,fa,num:array[0..1000000]of longint; bz:array[0..1000000]of boolean; procedure pd; var i:longint; begin for i:=1 to n do if (fa[i]=0)and(bz[i]=false) then begin inc(num[0]); num[num[0]]:=i; end; end; begin assign(input,'1.in');reset(input); readln(n); for i:=1 to n do begin read(a[i]); inc(fa[a[i]]); end; pd; repeat for i:=1 to num[0] do begin bz[num[i]]:=true; if bz[a[num[i]]]=false then begin inc(ans); bz[a[num[i]]]:=true; if fa[a[a[num[i]]]]>0 then dec(fa[a[a[num[i]]]]); end; end; num[0]:=0; pd; until num[0]=0; for i:=1 to n do begin if bz[i]=false then begin k:=a[i]; bz[i]:=true; tot:=1; while k<>i do begin bz[k]:=true; k:=a[k]; inc(tot); end; ans:=ans+tot div 2; end; end; writeln(ans); end.