3929. 【NOIP2014模拟11.6】创世纪 (Standard IO)
Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
Description
上帝手中有着n种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它，这样上帝就可以保持对世界的控制。由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题，我们知道上帝不是万能的，而且不但不是万能的，他甚至有事情需要找你帮忙——上帝希望知道他最多可以投放多少种世界元素，但是他只会O(2^n)级别的算法。虽然上帝拥有无限多的时间，但是他也是个急性子。你需要帮助上帝解决这个问题。
Input第一行一个正整数n，表示世界元素的数目。第二行n个正整数a_1, a_2, ..., a_n。a_i表示第i个世界元素能够限制的世界元素的编号。
Output最多可以投放的世界元素的数目。
Sample Input62 3 1 3 6 5
Sample Output3
样例说明：选择2、3、5 三个世界元素即可，分别有1、4、6来限制它们。Data Constraint30%的数据，n<=10。60%的数据，n<=10^5。100%的数据，a_i<=n<=10^6。
分析：
这道题有两种情况（有向）：独立环和环套树。对于环套树，我们在环上取点的时候，去一个便要隔一个再取。对于独立环，则是取一半个数的点即可，环套树把环和树分开做，最后加上独立环上取的点数即可。
代码：
const maxn=1000000; var indegree,limit:array [0..maxn] of longint; flag:array [0..maxn] of boolean; edge:array [0..1,0..maxn] of longint; n,ans,temp:longint; procedure init; var i,num:longint; begin readln(n); for i:=1 to n do begin read(num); limit[i]:=num; inc(indegree[num]); end; for i:=1 to n do if indegree[i]=0 then begin inc(edge[0,0]); edge[0,edge[0,0]]:=i; flag[i]:=true; end; end; procedure main; var i,j,num:longint; begin while edge[temp,0]<>0 do begin temp:=1-temp; edge[temp,0]:=0; for i:=1 to edge[1-temp,0] do begin if temp=1 then begin if not flag[limit[edge[1-temp,i]]] then begin inc(edge[temp,0]); edge[temp,edge[temp,0]]:=limit[edge[1-temp,i]]; flag[limit[edge[1-temp,i]]]:=true; end; end else begin dec(indegree[limit[edge[1-temp,i]]]); if (indegree[limit[edge[1-temp,i]]]=0) and (not flag[limit[edge[1-temp,i]]]) then begin inc(edge[temp,0]); edge[temp,edge[temp,0]]:=limit[edge[1-temp,i]]; flag[limit[edge[1-temp,i]]]:=true; end; end; end; if temp=1 then inc(ans,edge[temp,0]); end; for i:=1 to n do if (indegree[i]<>0) and (not flag[i]) then begin num:=0; j:=i; while not flag[j] do begin flag[j]:=true; j:=limit[j]; inc(num); end; inc(ans,num div 2); end; write(ans); end; begin assign(input,'century.in');reset(input); assign(output,'century.out');rewrite(output); init; main; close(input);close(output); end.
