看了进击的小牛大大的武侠风格并查集,以及港巨给我们录的视频,感慨良多~
QAQ:瑟瑟发抖的我~
港巨的"find"函数写的比较简洁,加上小牛大大的讲解,再看着港巨的代码,很容易理解(^oVo^~);按照港巨的思路,按部就班,一步一步来:
#include<bits/stdc++.h>
using namespace std;
int f[1006];
int find(int x){
if(x!=f[x]) //x去找自己的队长,先去问上一级
//f[x]=find(x);
f[x]=find(f[x]); //上一级不知道,接着去找上一级的上一级。直到找到.
return f[x];
}
int unite(int x,int y){
int fx=find(x); //fx是x的队长
int fy=find(y); //fy是y的队长
if(fx!=fy) //x和y的队长不是同一个人
f[fx]=fy; //俩队长打一架,谁赢谁当两队的队长(也可以f[fy]=fx)
}
int main(){
int n,m;
while(~scanf("%d",&n)&&n){
int j,k;
int ans=0;
scanf("%d",&m);
for(int i=1;i<=n;i++) //初始化,队长就位
f[i]=i;
for(int i=1;i<=m;i++){
scanf("%d %d",&j,&k);
// if(find(j)!=find(k))
unite(j,k); //先全部都找一遍,归队(看看谁和谁之前是一个队的) (并)
}
for(int i=1;i<=n;i++){
//if(i!=f[i])
if(i==find(i)) //这个人是队长 (查)
ans++; //队的数量加一 (集)
}
printf("%d\n",ans-1); //打ans-1次架就能把所有队集为一队
}
return 0;
}
再来看看另一种,区别和上一种不大,小牛大大武侠风的解释不要太迷人(^v^):参见小牛大大并查集讲解。
#include<bits/stdc++.h>
using namespace std;
int f[1006];
int find(int x){
if(x!=f[x]) //x去找自己的队长,先去问上一级
f[x]=find(f[x]); //上一级不知道,接着去找上一级的上一级。直到找到.
return f[x]; //队长
}
/*int unite(int x,int y){
int fx=find(x); //fx是x的队长
int fy=find(y); //fy是y的队长
if(fx!=fy) //x和y的队长不是同一个人
f[fx]=fy; //俩队长打一架,谁赢谁当两队的队长(也可以f[fy]=fx)
}*/ //主程序实现了并的操作
int main(){
int n,m;
while(~scanf("%d",&n)&&n){
int j,k;
scanf("%d",&m);
int ans=n-1; //把n个队结合成一个队,需要打n-1次架
for(int i=1;i<=n;i++) //初始化,队长就位
f[i]=i;
while(m--){ //m组人(一组俩人)
scanf("%d %d",&j,&k);
if(find(j)!=find(k)){ //j和k是不是同一队 (查)
f[find(j)]=find(k); //那就打架(j的队长和k的队长打) (并)
ans--; //打一次少一队(两队合为一队) (集)
}
}
printf("%d\n",ans); //打架次数
}
return 0;
}