什么是并查集呢，我相信大家都已经很熟悉了，在这里我就不再赘述。写这篇文章的主要目的不是新手教学，而是为了借POJ上相关的题目，全面的总结一下并查集问题和它的各个变种。
POJ 1611 The Suspects
题目大意:有n个学生（标号为0 to n-1),m个学生社团，给出每个社团里所有学生的标号，并假设0号学生患有SARS（社团里只要用一个学生患病，则整个社团里的学生都会被隔离），问最后一共会有多少学生被隔离？
这是一个最基础的并查集的应用，扫描每一个社团，只要两个学生出现在同一个社团，则将这两个集合合并起来，最后输出0号点所在集合的rank值集合（rank值记录这个集合中的元素个数并用一个flag值跟踪0号元素所在集合标号）即可。
这是并查集问题的第一种应用：集合合并，判断两点是不是在同一个集合，求某一个集合上的元素个数等。
#include<stdio.h>
#define MAX 30000
int f[MAX];//这里的1001只是一个示意性的数字 代表初始状态下的分支数目
int r[MAX];
int flag;
//由于不知道应该将子树挂到那个集合上面去，故需要一个准则，这里的准则是将子树挂到
//r值大的集合上面去,初始状态下r数组的值均为一，代表每个分支下只有一个数字
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}//查找函数，并压缩路径
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
if(a==flag)
flag=b;
}
else
{
f[b]=a;
r[a]+=r[b];
if(b==flag)
flag=a;
}
return 1;
}//合并函数，如果属于同一分支则返回0，成功合并返回1
int main()
{
int n,m;
int i,j;
int num;
int maxnum=0;
while(scanf("%d%d",&n,&m))
{
flag=0;
maxnum=0;
int temp1,temp2;
if(n==0&&m==0)
break;
for(i=0;i<n;i++)
{
f[i]=i;
r[i]=1;
}
for(j=1;j<=m;j++)
{
scanf("%d",&num);
for(i=0;i<num;i++)
{
if(i==0)
scanf("%d",&temp1);
else
{
scanf("%d",&temp2);
Union(temp1,temp2);
}
}
}
printf("%d\n",r[flag]);
}
return 0;
}
POJ 2492 A Bug's Life
个人认为它是初级并查集问题的一个升级。同时这个题让我看到了食物链的影子。。。
题目的大意是给出n只bug和m次观察到的性行为，并以此为依据判断两只bugs是不是有同性恋行为(gay)。
比如3只bug
1 2有性行为
2 3有性行为
1 3有性行为
---->>>>>首先1,2是异性。
---->>>>>然后2,3是异性。
可以推出1,3是异性。
但是1，3有性行为，所以可以判断出有一定有同性恋。
剥离这个题目所赋予的外壳，我们抽出这个问题的本质：并查集！
其实，这里最重要的是去维护每一个点到集合顶点的偏移量。（注意：下面生造了一个词 所谓集合元素 比如说f[i]=i,那么i就是集合元素，集合偏移量就是集合元素的偏移量）
初始状态下，应该是
i号点挂在i号集合下面
我们考虑一般情况：假设合并的过程已经进行了一部分 ，这样每一个集合下面都有元素，且各自对于顶点的偏移量都算出来了；
现在在a集合中的元素x和b集合中的元素y进行合并。此时有两中情况改变偏移量；
1.首先是集合的合并，如果要将a,b集合合并，又要保证x,y数字的kind不相同，比如说把b集合挂到a集合下面去。
代表集合的那个元素，他的偏移量永远是0，所以b要改变偏移量，使得b里面的y在进行变换后要和x相异。
如果 kind[x]=0;kind[y]=0;那么y对应的那个代表集合的元素的偏移量必须变成1，因为只有这样才能使得合并后，x,y有不同的kind;
如果 kind[x]=0,kind[y]=1;y对应代表集合的元素偏移量是0，所以对应集合偏移量还是0；
类推 kind[x]=1,kind[y]=0,同上,0；
kind[x]=1,kind[y]=1,y集合偏移量应该变为1；
综上 可以得到一个同或的关系。
用等式 kind
[a
]=(kind
[x
]+kind
[y
]+1)%2;恰好满足要求.
2.然后是压缩路径时候的偏移量改变
个人认为，这个主要是解决集合合并时候产生的“残余问题”，因为在合并集合的时候只是考虑了集合的偏移量，至于它下面的元素一概不管。一个压缩路径既分离了父子元素的偏移量，又使得子元素直接指向集合元素。
总而言之，并查集的操作就是不断地维护者各个集合中，每个元素身上对集合元素的偏移关系。从而确定他们是否具有同性恋。
在这个题中，假设是不存在同性恋的，所以只有找到矛盾才输出 有同性恋。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 2001
int f[MAX];
int kind[MAX];
int n,m;
int testcase;
void init()
{
int i;
for(i=1;i<=n;i++)
{
f[i]=i;
kind[i]=0;
}
}
int Find(int n)
{
if(f[n]==n)
return n;
int t=Find(f[n]);
kind[n]=(kind[n]+kind[f[n]])%2;
f[n]=t;
return f[n];
}
int Union(int x,int y)
{
int a=Find(x);
int b=Find(y);
if(a==b)
{
if(kind[x]==kind[y])
return 1;//1代表有同性恋情况
}
else
{
f[a]=b;
kind[a]=(kind[x]+kind[y]+1)%2;
}
return 0;
}
int main()
{
scanf("%d",&testcase);
int i,j;
int a,b;
int flag;
for(i=1;i<=testcase;i++)
{
flag=0;
scanf("%d%d",&n,&m);
init();
for(j=1;j<=m;j++)
{
scanf("%d%d",&a,&b);
if(Union(a,b))
{
flag=1;
}
}
if(flag==1)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",i);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",i);
}
return 0;
}
POJ 1182 食物链
中文题，让你输出假话的个数。其实这道题是上一道题的扩展，如果把上一道题也想成是食物链的话，就是1吃2，2吃1.
而这里是三个动物，所以同样是维护一个偏移量，只不过多了一位罢了。
程序的过程实质上就是在维护并查集，判断是否是假话是在维护的过程中进行的，只能算是附属品吧。
#include<iostream>
using namespace std;
#define MAX 50005
int f[MAX];
int kind[MAX];
int n,m;
void init()
{
int i;
for(i=1;i<=n;i++)
{
f[i]=i;
kind[i]=0;
}
}
int Find(int n)
{
if(f[n]==n)
return n;
int t=Find(f[n]);
kind[n]=(kind[n]+kind[f[n]])%3;
f[n]=t;
return f[n];
}
bool Union(int x,int y,int c)
{
if(x>n||y>n)
return 1;
int a=Find(x);
int b=Find(y);
if(c==1)
{
if(a==b)
{
if(kind[x]!=kind[y])
return true;
}
else if(a!=b)
{
f[b]=a;
kind[b]=(kind[x]-kind[y]+3)%3;
}
}
else
{
if(x==y)
return true;
if(a==b)
{
if((kind[x]+1)%3!=kind[y])
return true;
}
else if(a!=b)
{
f[b]=a;
kind[b]=(kind[x]-kind[y]+4)%3;
}
}
return false;
}
int main()
{
int i,j;
int a,b,c;
int sum=0;
scanf("%d%d",&n,&m);
init();
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&c,&a,&b);
if(Union(a,b,c))
sum++;
}
printf("%d\n",sum);
return 0;
}
这里将两个集合并起来并将所挂集合偏移量指向：
kind[b]
=(kind[x]-kind[y]+4)%3;
想想上一题是不是也很类似呢
其实上一题的公式也可以改成
kind[b]=(kind[x]-kind[y]+3)%2;
不管是几个动物循环，都能得到类似的结论，所以以后碰到4，5，6，7。。。个动物的食物链，你应该也会做了吧？^_^
POJ 1988 Cube Stacking
这道题更有意思了，说它开辟了并查集问题的新局面并不为过；上面2道题，研究的主要是到集合元素的偏移量，而这道题要求的是一个“逻辑上”到达集合元素的距离！集合合并的时候同样只修改被挂集合元素的距离值，残余部分留给压缩路径来处理.
如果理解了上面的问题，这个问题就很好理解了。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX 30000
int f[MAX+1];
int r[MAX+1];
int above[MAX+1];
void init()
{
int i;
for(i=1;i<=MAX;i++)
{
above[i]=0;
f[i]=i;
r[i]=1;
}
}
int realfather;
int find(int n)
{
int t;
if(f[n]==n)
{
realfather=n;
return n;
}
else
{
t=find(f[n]);
if(f[n]!=realfather)
above[n]+=(above[f[n]]);
f[n]=t;
}
return f[n];
}//查找函数，并压缩路径
void Union(int x,int y)
{
int a=find(x);
int b=find(y);
f[b]=a;
above[b]+=r[a];
r[a]+=r[b];
}//合并函数，如果属于同一分支则返回0，成功合并返回1
int main()
{
int p;
int i;
init();
char order;
int a,b;
scanf("%d",&p);
for(i=1;i<=p;i++)
{
cin.ignore();
scanf("%c",&order);
if(order=='M')
{
scanf("%d%d",&a,&b);
Union(a,b);
}
else if(order=='C')
{
scanf("%d",&a);
printf("%d\n",r[find(a)]-above[a]-1);
}
}
return 0;
}
银河英雄传说 NOI 2002
说道并查集，还有一道非常经典的题目 还有那个“著名”的杨威利元帅，呵呵。这题附上原题，有了上面的讲解，相信你能很快找到解法^_^
银河英雄传说
【问题描述】
公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。
宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
最终的决战已经展开，银河的历史又翻过了一页……
【输入文件】
输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。
以下有T行，每行有一条指令。指令有两种格式：
-
M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
-
C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
【输出文件】
输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
【样例输入】
4
M 2 3
C 1 2
M 2 4
C 4 2
【样例输出】
-1
1
【样例说明】
战舰位置图：表格中阿拉伯数字表示战舰编号
|
|
第一列
|
第二列
|
第三列
|
第四列
|
……
|
|
初始时
|
1
|
2
|
3
|
4
|
……
|
|
M 2 3
|
1
|
|
3
2
|
4
|
……
|
|
C 1 2
|
1号战舰与2号战舰不在同一列，因此输出-1
|
|
M 2 4
|
1
|
|
|
4
3
2
|
……
|
|
C 4 2
|
4号战舰与2号战舰之间仅布置了一艘战舰，编号为3，输出1
|
不知道并查集问题还有没有什么别的变种呢？除了维护偏移量和到顶点的距离，还有没有可能是别的情况呢？比如说。。。。。。如果你有更好的想法，欢迎和我交流。
文章由abilitytao原创
转载请注明出处：http://www.cppblog.com/abilitytao/archive/2009/10/18/98899.html