本文通过几道题介绍一下并查集的应用。
第一道题目：The Sus
pects
(http://acm.pku.edu.cn/JudgeOnline/problem?id=1611)
1. N个人编号,从0到N-1。
2. 给出这N个人分成M个集合的描述(同一个人可以加入不同的集合)。
求所有和0号有关系的集合的人数！
//用到并查集的3种基本操作
//并查集虽然用线性的数组，但是使用树
的操作。
#include <stdio.h>
int set[30001],i,j;
void MakeSet(int n)
//集合初始化为-1
//set[x]<0 表示x是根 并且它的所有结点的个数为该值的绝对值。
//初始可以看成，数组中每个元素是一个根，相互独立的集合。
{
for(i=0;i<n;i++)
set[i]=-1;
}
int FindSet(int a)
//查找含有a的集合的根
{
int i=a,t;
while(set[i]>=0) //递归查找直到找到根为止
i=set[i];
while(i!=a) //压缩路径，使得各个孩子直接指向根，以便下次搜索加速。
{
t=set[a];
set[a]=i;
a=t;
}
return i;
}
int UnionSet(int a,int b)
//合并含有a和b的集合。并返回合并后树的根
{
if(a==b)
return a;
if(set[a]>=set[b])
{
set[b]+=set[a]; //把2集合元素个数相加
set[a]=b; //把a的根设置为b
return b;
}
else
{
set[a]+=set[b]; //把2集合元素个数相加
set[b]=a; //把b的根设置为a
return a;
}
}
int main()
{
int number,a,b,n,m;
while(scanf("%d %d",&n,&m) && (n || m))
{
MakeSet(n);
for(i=0;i<m;i++)
{
scanf("%d",&number);
scanf("%d",&a);
a=FindSet(a); //找到第一个元素所在集合的根。
for(j=1;j<number;j++)
{
scanf("%d",&b);
b=FindSet(b); //找到这个元素b所在的集合
a=UnionSet(a,b); //把a和b合并，然后把合并后的根返回给a以便循环使用。
}
}
printf("%d/n",-set[FindSet(0)]); //寻找0所在集合的根，并且取绝对值。
}
return 1;
}
实际中不同的题目算法可能会有所变化，例如：增加rank标记，UnionSet也不一定非要返回合并后的根。
____________________________________________________________________________________
第二道题目：Ubiquitous Religions
(http://acm.pku.edu.cn/JudgeOnline/problem?id=2524)
2. 给出M对学生，他们信仰同一宗教
求在这所大学里最多可能有多少种不同的宗教？
根据并查集的思路，这样分析。
初始假设每个人宗教不同，也就有N种宗教。
每给出一对大学生M，合并2个集合。
最后循环找出有多少个独立的根就表示有多少中可能的宗教分支。
#include<stdio.h>
int set[50001],n;
void MakeSet()
{
int i;
for(i=1;i<=n;i++)
set[i]=-1; //这里假设每个人宗教都不同
}
int FindSet(int a)
{
int i=a,t;
while(set[i]>=0)
i=set[i];
while(i!=a)
{
t=set[a];
set[a]=i;
a=t;
}
return i;
}
void UnionSet(int a,int b)
//注意这里合并集合时候set[fa] set[fb]不相加。
//因为每个集合的元素个数没有用处。我们只希望求总集合数
{
int fa,fb;
fa=FindSet(a);
fb=FindSet(b);
if(fa<fb)
set[fb]=fa;
else if(fa>fb)
set[fa]=fb;
}
int output()
{
int ans=0,i;
for(i=1;i<=n;i++)
if(set[i]==-1) //这里可以看到，如果第i号人信的宗教=-1的话，哪就增加一个宗教分支。
ans++;
return ans;
}
int main()
{
int m,a,b,c=1;
while(scanf("%d %d",&n,&m),n||m){
MakeSet();
while(m--){
scanf("%d %d",&a,&b);
UnionSet(a,b);
}
printf("Case %d: %d/n",c++,output());
}
return 0;
}
____________________________________________________________________________________
第三道题目：Is It A Tree?
(http://acm.pku.edu.cn/JudgeOnline/problem?id=1308)
1. 给定一组有向关系集。
判断这组集合是否可以构成树！
例如系列3组关系形成树如下图：
6 8 5 3 5 2 6 4 5 6 0 0
8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0
3 8 6 8 6 4 5 3 5 6 5 2 0 0
思 路如下，利用并查集合并有向图。
1. 出现一个节点指向自己的父亲或祖先就说明不是树
2. 记录根结点的最大值，如果值!=全部结点个数,说明该图为森林，不算树
例如数据：
1 2 2 3 4 5 0 0 是森林不算是树
1 2 1 2 0 0 不是树（有2个相同的关系不是树）
0 0 空树是一棵树
#include<stdio.h>
#define n 50000
int set[n+1],mask[n+1]; //mask用来记录出现的
结
点
void MakeSet()
{
int i;
for(i=0;i<=n;i++)
{
set[i]=-1;
mask[i]=0;
}
}
int FindSet(int a)
{
int i=a,t;
while(set[i]>=0)
i=set[i];
while(i!=a)
{
t=set[a];
set[a]=i;
a=t;
}
return i;
}
int UnionSet(int a,int b)
//与上面2道题有些变化
//这次合并集合的时候始终按照a(父亲节点)->b(孩子节点)的方向，同时返回合并后树的
结
点个数
{
if(a!=b){
set[a]+=set[b];
set[b]=a;
}
return -set[a];
}
int main()
{
int a,b,fa,fb,c=1,f,num,max;
//max保存该图中出现的最大的结点数，如果不等于num(总结点数)表明为非连通图
while(scanf("%d%d",&a,&b) && !(a==-1 && b==-1))
{
MakeSet();
f=1;max=num=0;
if(a==0 && b==0);//0 0表示空树
else{
do{
if(f)
{
if(mask[a]==0)
{
num++;
mask[a]=1;
}
if(mask[b]==0)
{
num++;
mask[b]=1;
}
//记录节点总数
fa=FindSet(a);
fb=FindSet(b);
if(fa==fb) //如果同父结点或重复关系-不为树。
f=0;
if(set[fb]>=0) //入度节点已经有父结点-不为树
f=0;
int temp=UnionSet(fa,fb); //合并集合
if(temp>max)
max=temp;
}
} while(scanf("%d%d",&a,&b) && a && b);
}
if(f && max==num)
printf("Case %d is a tree./n",c++);
else
printf("Case %d is not a tree./n",c++);
}
}
____________________________________________________________________________________
第四道题目：
Wireless Network
(http://acm.pku.edu.cn/JudgeOnline/problem?id=2236)
1. 计算机网络由于地震受损，分成N台独立计算机。
2. 给定每台计算机的物理坐标(x,y)和2台计算机直接通信的最小距离d
3. 修复操作R(a)-修好计算机a.
4. 程序操作S(a,b)-查询计算机a,b是否可以通信并打印
模拟操作过程
思考:N台独立计算机为n个集合。利用并查集合并修复的计算机网络，如果网络间距离小于d。
查询操作S(a,b)相当于并查集中判断a元素所在集合和b元素所在集合是否相等！
#include <stdio.h>
#define N 1002
int d;
struct{
int p,c[2],s; //集合p表示根，c表示坐标(x,y) s表示该计算机是否修复 (1-修复 0-未修复)
} set[N];
void MakeSet(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
set[i].p=-1;
set[i].s=0;
}
}
int FindSet(int a)
{
int i=a,t;
while(set[i].p>0)
i=set[i].p;
while(i!=a)
{
t=set[a].p;
set[a].p=i;
a=t;
}
return i;
}
int UnionSet(int fa,int fb)
{
if(fa>fb){
set[fa].p+=set[fb].p;
set[fb].p=fa;
return fa;
}
set[fb].p+=set[fa].p;
set[fa].p=fb;
return fb;
}
int main()
{
int i,n,p,q,fp,fi;
char op;
scanf("%d%d",&n,&d);
d=d*d;
MakeSet(n);
for(i=1;i<=n;i++)
scanf("%d%d/n",&set[i].c[0],&set[i].c[1]);
while((op = getchar())!=EOF){
if(op=='O'){
//修复操作
scanf("%d/n",&p);
set[p].s=1;
fp=FindSet(p);
for(i=1;i<=n;i++)
//修复这个计算机和其他计算机网路的连接关系，循环使用并查集合并操作(当且距离满足条件时候)
{
if(i!=p && set[i].s){
if(((set[p].c[0]-set[i].c[0])*(set[p].c[0]-set[i].c[0])+(set[p].c[1]-set[i].c[1])*(set[p].c[1]-set[i].c[1]))<=d)
{
fi=FindSet(i);
if(fp!=fi) //当p和i计算机距离小于d并且不再同一集合内，合并！
fp=UnionSet(fp,fi);
}
}
}
}
else{
//查询操作当p和q的根相同时表明在同一网络。否则不可通信。
scanf("%d%d/n",&p,&q);
if(FindSet(p)==FindSet(q)) printf("SUCCESS/n");
else printf("FAIL/n");
}
}
return 0;
}