原題：

http://172.16.0.132/senior/#contest/show/2045/2

題目描述：

上帝手中有著n種被稱作“世界元素”的東西，現(xiàn)在他要把它們中的一部分投放到一個(gè)新的空間中去以建造世界。每種世界元素都可以限制另外一種世界元素，所以說上帝希望所有被投放的世界元素都有至少一個(gè)沒有被投放的世界元素能夠限制它，這樣上帝就可以保持對(duì)世界的控制。
由于那個(gè)著名的有關(guān)于上帝能不能制造一塊連自己都不能舉起的大石頭的二律背反命題，我們知道上帝不是萬能的，而且不但不是萬能的，他甚至有事情需要找你幫忙——上帝希望知道他最多可以投放多少種世界元素，但是他只會(huì)O(2^n)級(jí)別的算法。雖然上帝擁有無限多的時(shí)間，但是他也是個(gè)急性子。你需要幫助上帝解決這個(gè)問題。

輸入：

第一行一個(gè)正整數(shù)n，表示世界元素的數(shù)目。
第二行n個(gè)正整數(shù)a_1, a_2, ..., a_n。a_i表示第i個(gè)世界元素能夠限制的世界元素的編號(hào)。

輸出：

最多可以投放的世界元素的數(shù)目。

樣例輸入：

6
2 3 1 3 6 5

樣例輸出：

3

樣例說明：

選擇2、3、5 三個(gè)世界元素即可，分別有1、4、6來限制它們。

數(shù)據(jù)范圍限制：

30%的數(shù)據(jù)，n<=10。
60%的數(shù)據(jù)，n<=10^5。
100%的數(shù)據(jù)，a_i<=n<=10^6。

分析：

貪心。
找出所有沒有入度的點(diǎn)，那么這些點(diǎn)必定不能選入集合中，我們沿著這些點(diǎn)上溯，將可以選進(jìn)集合的點(diǎn)都選進(jìn)集合。
這里“可以選進(jìn)”的定義為存在一個(gè)沒有被選進(jìn)集合的前驅(qū)。
于是環(huán)上就會(huì)有若干個(gè)由樹上決定它要選進(jìn)集合的點(diǎn)。
我們將環(huán)按照已選入集合的點(diǎn)來分裂成若干段，每一段按照原來的貪心方法來貪心即可。

貪心正確性的證明：

我們將一個(gè)點(diǎn)從“選”的狀態(tài)變成不選，顯然不會(huì)改變其前驅(qū)的狀態(tài)（前驅(qū)并不依賴于這個(gè)點(diǎn)），那么我們考慮一下后繼的情況。
如果這個(gè)點(diǎn)x的唯一的后繼y并沒有被選入，那么說明它原來所有的前驅(qū)都被選入了。我們可以將它選入點(diǎn)集中。但是這樣子可能導(dǎo)致y的唯一后繼z無法被選入了（這種情況就是z被選入點(diǎn)集時(shí)依賴于y），從下圖可以更直觀地看出這種關(guān)系。

圖片1.png

那么這時(shí)候我們就可以有兩種選擇，直接舍棄綠叉邊，又或者將它繼續(xù)往下“推”，那么遞歸地來看這和我們做的第一步是相同的，顯然這么做并不能使得被選入邊集的邊數(shù)增多。
如果這個(gè)點(diǎn)x的唯一的后繼y被選入了，那么情況是類似的，不難證明不會(huì)使得邊數(shù)增多。
綜上所述，通過上面所述的貪心策略能選出最大的點(diǎn)集。

實(shí)現(xiàn)：

#include<cstdio>

const int maxn=1000010;  
int a[maxn],team[maxn],head,tail,n;  
int rd[maxn];  
int ans;  
bool bz[maxn];  
  
int main()  
{  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
        scanf("%d",&a[i]),rd[a[i]]++;  
    for(int i=1;i<=n;i++)  
        if(!rd[i])  
            team[++tail]=i;  
    while(head<tail)  
    {  
        int t=team[++head];  
        if(!bz[t]&&!bz[a[t]])  
        {  
            bz[a[t]]=1;  
            ans++;  
            if(!--rd[a[a[t]]])  
            {  
                team[++tail]=a[a[t]];  
            }  
        }  
        bz[t]=1;  
    }  
    for(int i=1;i<=n;i++)  
    {  
        if(!bz[i])  
        {  
            int t=1;  
            bz[i]=1;  
            int c=i;  
            while(a[c]!=i)  
            {  
                c=a[c];  
                bz[c]=1;  
                t++;  
            }  
            ans+=t>>1;  
        }  
    }  
    printf("%d",ans);
}