【bzoj1529】[POI2005]ska Piggy banks Tarjan

题目描述

Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.

输入

第一行一个整数 N (1 <= N <= 1.000.000) – 表示存钱罐的总数. 接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.

输出

一个整数表示最少打破多少个存钱罐.

样例输入

4
2
1
2
4

样例输出

2

---

题解

Tarjan裸题

加x->a[x]的边，求的就是出度为0的强连通分量的个数。（反过来加也可以，就是很麻烦）

#include <cstdio>
#include <algorithm>
using namespace std;
int a[1000010] , deep[1000010] , low[1000010] , tot , sta[1000010] , top , vis[1000010] , ins[1000010] , bel[1000010] , cnt , cd[1000010];
void tarjan(int x)
{
    deep[x] = low[x] = ++tot;
    ins[x] = vis[x] = 1;
    sta[++top] = x;
    if(!vis[a[x]])
        tarjan(a[x]) , low[x] = min(low[x] , low[a[x]]);
    else if(ins[a[x]])
        low[x] = min(low[x] , deep[a[x]]);
    if(deep[x] == low[x])
    {
        int t;
        cnt ++ ;
        do
        {
            t = sta[top -- ];
            ins[t] = 0;
            bel[t] = cnt;
        }while(t != x);
    }
}
int main()
{
    int n , i , ans = 0;
    scanf("%d" , &n);
    for(i = 1 ; i <= n ; i ++ )
        scanf("%d" , &a[i]);
    for(i = 1 ; i <= n ; i ++ )
        if(!vis[i])
            tarjan(i);
    for(i = 1 ; i <= n ; i ++ )
        if(bel[i] != bel[a[i]])
            cd[bel[i]] ++ ;
    for(i = 1 ; i <= cnt ; i ++ )
        if(!cd[i])
            ans ++ ;
    printf("%d
" , ans);
    return 0;
}