题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1529

题意:

  Byteazar有N个小猪存钱罐。

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

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

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

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

题解:

  并查集。

  

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

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

  

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

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

AC Code:

 #include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005 using namespace std; int n;
int ans=;
int par[MAX_N]; void init_union_find()
{
for(int i=;i<=n;i++)
{
par[i]=i;
}
} int find(int x)
{
return par[x]==x?x:par[x]=find(par[x]);
} void unite(int x,int y)
{
int px=find(x);
int py=find(y);
if(px==py) return;
par[px]=py;
} bool same(int x,int y)
{
return find(x)==find(y);
} void read()
{
cin>>n;
init_union_find();
int a;
for(int i=;i<=n;i++)
{
cin>>a;
unite(i,a);
}
} void solve()
{
for(int i=;i<=n;i++)
{
if(find(i)==i) ans++;
}
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}
04-13 11:05