并查集总结

程序员文章站 2022-03-24 17:29:20

...

刚刚接触并查集，有理解不当的地方，还望不吝指教。

先引入定义：并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。

最近在poj上做好好几道并查集的题目，个人感觉并查集的基本思路是这样的：通过合并使不相交集合之间产生关系，再利用查找方法来优化路径并更新集合中结点的信息。

一般方法
先定义结点类型
struct _node {
int parent;//必不可少，如有必要，可再添加其他属性
}NODE[length];

初始化方法
void Init(int n){
int i;
for(i=0;i<n;i++){
NODE[i].parent=i;
}
}
此时各结点单独构成不相交的集合。

查找方法
int Find(int index){
if(index==NODE[index].parent){
return index;
}else {
NODE[index].parent=Find(NODE[index].parent);
//如有必要，此时就对结点的相关属性进行更新
return NODE[index].parent;
}
}合并方法，注意，此时的操作是针对根结点的
void Unions(int x,int y){
int rx,ry;
rx=Find(x);
ry=Find(y);
NODE[rx].parent=ry;
//如果需要，对根结点进行相应的操作
}

以下是几道题的解题报告
POJ 1988 Cube Stacking
[url]http://poj.org/problem?id=1988[/url]
这道题是并查集里面最简单也是最典型的题型
题意是大体是这样的，当输入M X Y时，就将X所在这一堆方块堆到Y所在的那一堆上；当输入C X时，就计算一下X下面有几个方块。以下是AC代码（作用GCC编译器）：

[b][color=red]#include <stdio.h>

struct point{
	int parent;
	int sum;
	int ans;
}cube[100005];

void Init(int n){
	int i;
	for(i=1;i<=n;i++){
		cube[i].parent=i;
		cube[i].sum=1;
		cube[i].ans=0;
	}	
}

int Find(int index){
	int temp;
	if(index==cube[index].parent){
		return index;
	}else {	
		temp=cube[index].parent;
		cube[index].parent=Find(cube[index].parent);
		cube[index].ans+=cube[temp].ans;
		return cube[index].parent;
	}
}

void Unions(int rx,int ry,int x,int y){
	cube[rx].parent=ry;
	cube[rx].ans=cube[ry].sum;
	cube[ry].sum+=cube[rx].sum;
}

int main(int argc, char *argv[])
{
	int p,x,y,s;
	char c;
	scanf("%d",&p);
	Init(30010);
	while(p--){
		scanf("\n%c",&c);
		if(c=='M'){
			scanf(" %d %d",&x,&y);
			int rx,ry;
			rx=Find(x);
			ry=Find(y);
			Unions(rx,ry,x,y);
		}else if(c=='C'){
			scanf(" %d",&s);
			Find(s);
			printf("%d\n",cube[s].ans);
		}
	}	
	return 0;
}[/color][/b]

解释一下：
struct point{
int parent;
int sum;
int ans;
}cube[100005];
每一个结点有三个属性值：根结点，所在堆的总方块数，以及它下面的方块数。由此可以很简单的推出初始化方法
void Init(int n){
int i;
for(i=1;i<=n;i++){
cube[i].parent=i;//集合独立
cube[i].sum=1;//总方块数为1
cube[i].ans=0;//下面没有方块
}
}
先说合并方法
void Unions(int rx,int ry,int x,int y){
cube[rx].parent=ry;
cube[rx].ans=cube[ry].sum;
cube[ry].sum+=cube[rx].sum;
}
在合并时，令下面那一堆的根结点为新堆的根结点。此时，X堆的根结点下面的方块数就为Y堆原来的总方块数，新堆的总数为两堆总数之和。

int Find(int index){
int temp;
if(index==cube[index].parent){
return index;
}else {
temp=cube[index].parent;
cube[index].parent=Find(cube[index].parent);
cube[index].ans+=cube[temp].ans;
return cube[index].parent;
}
}
只需要解释cube[index].ans+=cube[temp].ans ，在合并之后，结点的ans值并没有因此而改变，所以应该在Find方法里进行更新，此时结点下面的方块数应该是它原来的方块数加上它本来的根结点的方块数。

此题是入门题目，所以讲得有点详细。。。

POJ 1611 The Suspects
[url]http://poj.org/problem?id=1611[/url]
AC 源代码（GCC你懂的）

[color=red][b]#include <stdio.h>

struct _node{
	int parent;
}suspect[30000];

void Init(int n){
	int i;
	for(i=0;i<n;i++){
		suspect[i].parent=i;
	}
}

int Find(int index){
	int temp;
	if(index!=suspect[index].parent){
		suspect[index].parent=Find(suspect[index].parent);
	}
}

void Unions(int x,int y){
	int rx,ry;
	rx=Find(x);
	ry=Find(y);
	suspect[ry].parent=rx;
}

int main(int argc, char *argv[])
{
	int n,m,num,id1,id2,group0,i,j,sum;
	for(scanf("%d %d",&n,&m);n!=0;scanf("%d %d",&n,&m)){
		Init(n);
		getchar();
		if(n==0 && m==0){
			return 0;
		}
		for(i=0;i<m;i++){
			scanf("%d %d",&num,&id1);
			for(j=1;j<num;j++){
				scanf("%d",&id2);
			   Unions(id1,id2);
			}
			getchar();
		}		
		group0=Find(0);
		sum=0;
		for(i=0;i<n;i++){
			if(Find(i)==group0){
				sum++;	
		}
	}
		printf("%d\n",sum);
	}    
	return 0;
}[/b][/color]

1703 Find them, Catch them
[url]http://poj.org/problem?id=1703[/url]
题意是这样的，有两伙人，当输入D X Y的时候，表示X Y不在一伙，当输入A X Y时，判断X Y是否是一伙的，输入相应的"In the same gang.", "In different gangs." and "Not sure yet."。

[b]#include <stdio.h>
struct _node{
	int parent;
	int gang;//0表示与根结点是一伙的，1表示不是一伙的
}NODE[100010];

void Init(){
	for(i=0;i<100010;i++){
		NODE[i].parent=i;
		NODE[i].gang=0;
	}
}
/*蓝色字部分可以简化为NODE[n].gang=NODE[temp].gang==0?NODE[x].gang:(NODE[temp].gang+1)%2;思路是这样的，如果它原来的根结点与现在的根结点是一样的，那么它的gang值就不用改变，如果不是，那么要让它成为另外一伙的。当然(NODE[temp].gang+1)%2与1-NODE[temp].gang的处理是等价的，但前者应用起来更有普适性。*/
int Find(int n){
	int temp;
	if(n!=NODE[n].parent){
		temp=NODE[n].parent;
		NODE[n].parent=Find(NODE[n].parent);
		[color=blue]if(NODE[n].gang==0){
			NODE[n].gang=NODE[temp].gang;
		}else{
			NODE[n].gang=(NODE[temp].gang+1)%2;
		}
	}[/color]	return NODE[n].parent;
}
/*
黄字部分是这样推出来的：如果NODE[x].gang==NODE[y].gang==0,说明x与rx一伙，y与ry一伙，但是x,y不是一伙的，所以令NODE[ry].gang=1;都等于1时也一样。同理，NODE[x].gang与NODE[y].gang不相等时，要令NODE[ry].gang=0;
*/
void Unions(int x,int y){
	int rx,ry;
	rx=Find(x);
	ry=Find(y);
	NODE[ry].parent=rx;
	[color=yellow]NODE[ry].gang=(NODE[x].gang==NODE[y].gang)?1:0;[/color]}
//主函数就不用解释了吧。。
int main(int argc, char *argv[])
{
	int t,n,m,a,b;
	char c;
	scanf("%d\n",&t);

	while(t--){
		scanf("%d %d\n",&n,&m);
		Init();
		while(m--){
			scanf("%c %d %d",&c,&a,&b);
			getchar();
			if(c=='D'){
				Unions(a,b);
			}else if(c=='A'){
				int rx,ry;
				rx=Find(a);
				ry=Find(b);
				if(rx!=ry){
					printf("Not sure yet.\n");
				}else{
					if(NODE[a].gang!=NODE[b].gang){
						printf("In different gangs.\n");
					}else{
						printf("In the same gang.\n");
					}
				}
			}			
		}
	}	
	return 0;
}[/b]

POJ 1182 食物链
[url]http://poj.org/problem?id=1182[/url]
这道题是中文题，题意就自己看吧。。
这道题的公式推起来是最麻烦的。先看代码

[color=red]#include <stdio.h>

struct point{
	int parent;
	int kind;
}ufind[50010];

void Init(int n){
	int i;
	for(i=0;i<n;i++){
		ufind[i].parent=i;
		ufind[i].kind=0;
	}
}

int Find(int index){
	int temp;
	if(index==ufind[index].parent){
		return index;
	}else{
		temp=ufind[index].parent;
		ufind[index].parent=Find(ufind[index].parent);
		ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
/*
上面这句话是这样推出来的。[img]

[img]http://dl.iteye.com/upload/attachment/482883/568157c8-19bf-3e3d-a7e8-dac6576528fa.png[/img]
[/img]如果原根结点与现在的根结点同类，而此结点与原根结点是同类的，那么他现在的类型还是0.如果此结点吃原根结点，那么他还是吃现在的根结点。如果它被原根结点吃，那么他还是被现在的结点吃。同理可推出上表的关系，从而推出ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
*/
		return ufind[index].parent;
	}
}

void Unions(int rootx, int rooty, int x, int y, int d)
{
    ufind[rooty].parent=rootx;
	ufind[rooty].kind=(-(d-1)+(ufind[x].kind-ufind[y].kind)+3)%3;
/*
上面的公式是这样推出来的，先根据d的值分类讨论，如果d为1的话，那么y的类型要设为x的类型,而rooty的类型就设为|x.kind-y.kind|;如果d为2的话，那么y的类型应该是(x.kind-1+3)%3,而rooty的类型还要在此基础上加上|x.kind-y.kind|;综上，可得到ufind[rooty].kind=(-(d-1)+(ufind[x].kind-ufind[y].kind)+3)%3;
*/
}

int main(){
	int n,k,d,x,y,sum=0,rx,ry;
	scanf("%d %d",&n,&k);
	Init(n);
	while(k--){
		scanf("%d %d %d",&d,&x,&y);
//当前的话中X或Y比N大，就是假话； 
		if(x>n||y>n){
			sum++;
		}else 
//当前的话表示X吃X，就是假话。
if(d==2 && x==y){
			sum++;
		}else {
			rx=Find(x);
			ry=Find(y);
			if(rx!=ry){
				Unions(rx,ry,x,y,d);
			}
//当前的话与前面的某些真的话冲突，就是假话；
else{
				if(d==1 && ufind[x].kind!=ufind[y].kind)
                      sum++;
                if(d==2 && (ufind[x].kind-ufind[y].kind+3)%3!=1)
                      sum++;
			}
		}		
	}
	printf("%d\n",sum);
	return 0;
}[/color]

并查集总结

sql server连接oracle并实现增删改查

python 集合并集、交集 Series list set 转换的实例

tp5(thinkPHP5)框架数据库Db增删改查常见操作总结

SQL语句的并集UNION 交集JOIN(内连接，外连接)等介绍

面试题查找婴儿同名频率和数量（并查集，代码超时了）

sql 中并集union和union all的使用区别

【TOJ 5224】排座位（并查集+二维数组）

C#SuperSocket的搭建并配置启动总结

LibreOJ #109. 并查集

sqlserver查询（子查询，全连接，等值连接，自然连接，左右连，交集，并集，差集）

并查集总结

sql server连接oracle并实现增删改查

python 集合 并集、交集 Series list set 转换的实例

tp5(thinkPHP5)框架数据库Db增删改查常见操作总结

SQL语句的并集UNION 交集JOIN(内连接，外连接)等介绍

面试题查找婴儿同名频率和数量（并查集，代码超时了）

sql 中 并集union和union all的使用区别

【TOJ 5224】排座位（并查集+二维数组）

C#SuperSocket的搭建并配置启动总结

LibreOJ #109. 并查集

sqlserver查询（子查询，全连接，等值连接，自然连接，左右连，交集，并集，差集）

python 集合并集、交集 Series list set 转换的实例

sql 中并集union和union all的使用区别