题目链接：

题意：

　　Byteazar有N个小猪存钱罐。

　　每个存钱罐只能用钥匙打开或者砸开。

　　Byteazar已经把每个存钱罐的钥匙放到了某些存钱罐里。

　　Byteazar 现在想买一台汽车于是要把所有的钱都取出来。

　　他想尽量少的打破存钱罐取出所有的钱，问最少要打破多少个存钱罐。

 

题解：

　　并查集。

　　

　　如果打开a的钥匙放在b中，那么如果打开了b，a也能打开。

　　所以将a的认爹箭头指向b。

　　

　　对于一个集合，只要打开了这个集合的老大，那么其他的就都能打开。

　　所以答案为集合个数。也就是统计find(i) == i的点的个数。

 

AC Code:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAX_N 1000005 5  6 using namespace std; 7  8 int n; 9 int ans=0;10 int par[MAX_N];11 12 void init_union_find()13 {14     for(int i=1;i<=n;i++)15     {16         par[i]=i;17     }18 }19 20 int find(int x)21 {22     return par[x]==x?x:par[x]=find(par[x]);23 }24 25 void unite(int x,int y)26 {27     int px=find(x);28     int py=find(y);29     if(px==py) return;30     par[px]=py;31 }32 33 bool same(int x,int y)34 {35     return find(x)==find(y);36 }37 38 void read()39 {40     cin>>n;41     init_union_find();42     int a;43     for(int i=1;i<=n;i++)44     {45         cin>>a;46         unite(i,a);47     }48 }49 50 void solve()51 {52     for(int i=1;i<=n;i++)53     {54         if(find(i)==i) ans++;55     }56 }57 58 void print()59 {60     cout<
        
         <