算法训练 - HDU1232-畅通工程[并查集入门]
HDU:http://acm.hdu.edu.cn/showproblem.php?pid=1232
Problem Description:
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
Input:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
Output:
对每个测试用例,在1行里输出最少还需要建设的道路数目。
Sample Input:
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999
0
0
Sample Output
1
0
2
998
Source :浙大计算机研究生复试上机考试-2005年
--------------------------------------------------题目分析-----------------------------------------------
题解:问还需要修几条路,实质就是求有几个连通分支。
如果是1个连通分支,说明整幅图上的点都连起来了,不用再修路了;
如果是2个连通分支,则只要再修1条路,从两个分支中各选一个点,把它们连起来,那么所有的点都是连起来的了;
如果是3个连通分支,则只要再修两条路……
---------------------------------------------------并查集------------------------------------------------
并查集由一个整数型的数组和两个函数构成。
数组pre[]记录了每个点的前导点[老大]是什么( 函数find是查找+join是合并 )
pre[8]=5;pre[5]=2;pre[2]=1;
pre[6]=3;pre[3]=1;
pre[7]=4;pre[4]=1;
1. find(int root)函数:找root结点的boss。
ex:find(8)=1 表示找到结点8的boss是1;
2. join(int x,int y)函数:两个结点,一个x,一个y。目的是将x和y相连(判断x的boss==y的boss?
如果等于的话,那么可不用相连;
如果不等于的话,那么将y设置为x的父结点,即:pre[x]=y)。
join(7,8) : 因7的boss为父结点1,11的boss为父结点0,所以表示将结点7与11相连,即:pre[7]=11。
join(3,4):因3和4的boss都为同一个boss(父结点1),所以不做任何的改变。
实现代码:
int pre[1010];//存放第i个元素的父结点
int find(int root){
int son=root;//先保存当前儿子节点
while(root!=pre[root]){
root=pre[root];
}
//路径压缩[将所有子节点(包括间接相连的结点)变为父结点的直系结点]
int temp;
while(son!=root){
temp=pre[son]; //在改变上级之前先保存[现上级结点]
pre[son]=root; //把上级改为根节点
son=temp;
}
return root;
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
pre[fx]=fy;
}
}
---------------------------------------------------完整代码----------------------------------------------------------
#include<iostream>
#include<cmath>
using namespace std;
int pre[1010];//存放第i个元素的父结点
int find(int root){
int son=root;//先保存当前儿子节点
while(root!=pre[root]){
root=pre[root];
}
//路径压缩[将所有子节点(包括间接相连的结点)变为父结点的直系结点]
int temp;
while(son!=root){
temp=pre[son]; //在改变上级之前先保存[现上级结点]
pre[son]=root; //把上级改为根节点
son=temp;
}
return root;
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
pre[fx]=fy;
}
}
int main(){
int n;
while(cin>>n){
if(n==0) break;
//初始化[把每个结点的boss都定义为自己本身]
for(int i=1;i<=n;i++){
pre[i]=i;
}
int m;
cin>>m;
//道路相连
int a,b;
while(m--){
cin>>a>>b;
join(a,b);
}
//遍历pre[],记录有多少个boss(boss的判断条件:pre[i]=i)。
int count=0;
for(int i=1;i<=n;i++){
if(pre[i]==i){
count++;
}
}
cout<<count-1<<endl;//boss-1即为所求
}
return 0;
}
END:AC...