首页 > 代码库 > 并查集
并查集
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。
定义：并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。
主要操作
初始化
查找
合并
实例
描述：
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
Input:
第一行：三个整数n,m,p，（n< =5000,m< =5000,p< =5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1< =Mi，Mj< =N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
OutPut:
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
方法一：单链表实现
一个节点对应一个人，在同一个集合中的节点串成一条链表就得到了单链表的实现。在集合中我们以单链表的第一个节点作为集合的代表元。于是每个节点x（x也是人的编号）应包含这些信息：指向代表元即表首的指针head[x]，指向表尾的指针tail[x]，下一个节点的指针next[x]。
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1000000
int head[MAXSIZE],tail[MAXSIZE],next[MAXSIZE];//指向代表袁既表首指针，指向表尾指针，下一个节点的指针
//建立单个人的集合
void SUB_Make_Set(int num)
{
int i;
for(i=1;i<=num;i++)
{
head[i]=i;
tail[i]=i;
next[i]=0;
}
}
//确认x所在集合的代表元素
int SUB_Find_Set(int x)
{
return head[x];
}
//将b所在的集合合并到a所在的集合
void SUB_Union(int a,int b)
{
next[tail[head[a]]]=head[b];
tail[head[a]]=tail[head[b]];
int p = head[b];
while(p!=0)
{
head[p]=head[a];
p=next[p];
}
}
int main()
{
int n,m,p,i,mi,mj;
scanf("%d%d%d",&n,&m,&p);
SUB_Make_Set(n);
printf("请输入%d组亲戚关系：\n",m);
while(m--)
{
scanf("%d%d",&mi,&mj);
if(SUB_Find_Set(mi)!=SUB_Find_Set(mj))
{
SUB_Union(mi,mj);
}
}
printf("请输入%d组询问亲戚关系：\n",p);
while(p--)
{
scanf("%d%d",&mi,&mj);
if(SUB_Find_Set(mi)==SUB_Find_Set(mj))
{
printf("Yes\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
方法二：并查集深林
并查集的另一种更快的实现是用有根树来表示集合：每棵树表示一个集合，树中的节点对应一个人。
每个节点x包含这些信息：父节点指针p[x]，树的深度rank[x]。其中rank[x]将用于启发式合并过程。
还有另一种优化方法（未实现）：路径压缩：
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1000000
int p[MAXSIZE],rank[MAXSIZE];//父节点指针和深度
//初始化节点
void SUB_Make_Set(int x)
{
p[x]=x;
rank[x]=0;
}
//找出x的代表元素，既x树的根节点 （若两个节点的代表元素相同则说明这两个节点属于同一结合中）
int SUB_Find_Set(int x)
{
if(x==p[x])//遇到根节点返回
{
return x;
}
else//递归查找
{
return SUB_Find_Set(p[x]);
}
}
//合并a和b树
void SUB_Union(int a,int b)
{
int pa,pb;
//找出a树和b树的根节点
pa = SUB_Find_Set(a);
pb = SUB_Find_Set(b);
if(rank[pa]>rank[pb])//若a树的层数小于b树的层数，则将a树合并到b树中
{
p[pb]=pa;
}
else//合作b树合并到a树中
{
p[pa]=pb;
if(rank[pa]==rank[pb])//若两树层次相等，则合并后层次要加1
{
rank[pb]++;
}
}
}
int main()
{
int n,m,p,i,mi,mj;
scanf("%d%d%d",&n,&m,&p);
for(i=1;i<=n;i++)//初始化离散的节点
{
SUB_Make_Set(i);
}
printf("请输入%d组亲戚关系：\n",m);
while(m--)
{
scanf("%d%d",&mi,&mj);
if(SUB_Find_Set(mi)!=SUB_Find_Set(mj))//如果mi和mj还未属于同一集合中时需要进行合并操作
{
SUB_Union(mi,mj);
}
}
printf("请输入%d组询问亲戚关系：\n",p);
while(p--)
{
scanf("%d%d",&mi,&mj);
if(SUB_Find_Set(mi)==SUB_Find_Set(mj))
{
printf("Yes\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
并查集