本文主要是介绍hdu 1232 畅通工程【并查集】【模板题】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu 1232 畅通工程
#include<iostream>
#include<string.h>
using namespace std;
int pre[1005];
int find (int x)
{int r=x;while(pre[r]!=r)r=pre[r];int i=x;int j;while(i!=r){j=pre[i];pre[i]=r;i=j;}return r;
}
void join (int x,int y)
{int fx=find(x); //选择根节点int fy=find(y);if (fx!=fy){pre[fx]=fy;}
}int main()
{int N,M,a,b,i;while(cin>>N>>M && N){for(i=1;i<=N;i++)//初始化pre[] {pre[i]=i;//每个城市都是独立的。把=写成了==，找了好久的bug }for(i=1;i<=M;i++){cin>>a>>b;join(a,b);}int ans=0;for(i=1;i<=N;i++){//if(i==find(i))//找到一个根节点，ans++ if(pre[i]==i){ans++;} }
// for(int i=1;i<=N;++i) //【测试】依次输出1～n的根节点
// cout<<find(i)<<" ";
// cout<<endl;cout<<ans-1<<endl;}return 0;
}
//另开一个数组t[],存是不是根节点
#include<cstring>
#include<iostream>
using namespace std;
int pre[1005];
int find(int x)
{int r=x;while(r!=pre[r]) //寻找根节点,(pre[r]是 r 的 上级，) r=pre[r];int i=x,j;while(i!=r) //压缩路径，使得每一个子节点的上级直接为根节点，省去层层回溯 { j=pre[i];pre[i]=r;i=j;}return r;
}void join(int a,int b)
{ int fx=find(a); //选择根节点int fy=find(b); //选择根节点 if(fx!=fy) //若相等，即为同一根节点，否则，用跟节点进行合并 {pre[fx]=fy; //根节点合并 }
} int main()
{int n,m;while(cin>>n>>m&&n){bool t[1005]; //用来做最终统计 int ans=-1;memset(t,0,sizeof(t));for(int i=1;i<=n;++i)pre[i]=i; //初始化 int a,b;for(int i=1;i<=m;++i){cin>>a>>b;join(a,b); //合并操作 }for(int i=1;i<=n;++i)//i是根节点，t[i]=1 t[(find(i))]=1; for(int i=1;i<=n;++i)//统计根节点个数 if(t[i])ans++;
// for(int i=1;i<=n;++i) //【测试】依次输出1～n的根节点
// cout<<find(i)<<" ";
// cout<<endl;
// for(int i=1;i<=n;++i) //【测试】i是根节点，t[i]=1 ，否则 t[i]=0
// cout<<t[i]<<" ";
// cout<<endl; cout<<ans<<endl;}return 0;
}
这篇关于hdu 1232 畅通工程【并查集】【模板题】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
