题目链接: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();
}