首页 > 代码库 > 并查集

并查集

在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能采用一种全新的抽象的特殊数据结构——并查集来描述。

  定义:并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合,也就是按一定顺序将属于同一组的元素所在的集合合并。

主要操作

  初始化

    把每个点所在集合初始化为其自身。
    通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。

查找

    查找元素所在的集合,即根节点。

合并

    将两个元素所在的集合合并为一个集合。
    通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。

实例

描述:
  若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 
  规定: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;
} 

并查集