并查集最小生成树.ppt

并查集（Disjoint Set）
导引问题
在某个城市里住着n个人，现在给定关于 n个人的m条信息（即某2个人认识），

假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？
Hd 12
4
11
1
10
12
9
8
20
21
16
示例—畅通工程(HDOJ-1232)
题目描述：
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
题目分析
最赤裸裸的并查集，无话可说～
附:参考源码(HDOJ-1232)
#include ""
int bin[1002];
int findx(int x)
{
int r=x;
while(bin[r] !=r)
r=bin[r];
return r;
}
void merge(int x,int y)
{
int fx,fy;
fx = findx(x);
fy = findx(y);
if(fx != fy)
bin[fx] = fy;
}
int main()
{
int n,m,i,x,y,count;
while(scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
bin[i] = i;
for(scanf("%d",&m);m>0;m--)
{
scanf("%d %d",&x,&y);
merge(x,y);
}
for(count=-1, i=1;i<=n;i++)
if(bin[i] == i)
count ++;
printf(“%d\n”,count);//集合的个数就是不连通分支的个数。要修建道路就是不连通分支减1。
}
}
How Many Tables HDOJ 1213
Problem Description
生日聚会，认识的人可以做一张桌子。If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.Sample Input
2
5 3 （5个人，3个关系）
1 2
2 3
4 5
5 1
2 5Sample Output
2
4
#include <cstdio>
#include <iostream>
using namespace std;
int bin[1100];
find3(int x)
{int r,i,j;
r = x;
while (bin[r] != r) //循环结束，则找到根节点
r = bin[r];
i = x;
while (i !=r) //本循环修改查找路径中所有节点
{
j = bin[i];
bin[i] = r;
i = j;
}
return r;
}
void merge(int x,int y)
{
int fx,fy;
fx = find3(x);
fy = find3(y);
if(fx != fy)
bin[fx] = fy;
}
int main()
{
int n , m,i ;
int count;
int ccase;
int x,y;
scanf("%d",&ccase);
while( ccase--)
{
scanf("%d%d" , &n,&m) ;
for( i=1; i<=n; i++ )
bin[i] = i;
for(i=1; i<=m;