并查集

常见两种操作：
第一种方法：
合并两个集合（代码效率不高）

merge1(a,b)
{
	i=min(a,b);
	j=max(a,b);
	for(i=0;i<=N;i++)
	{
		if(set[k]==j)
		{
			set[k]=i;
		}
	}
 } 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

对数组的所有元素进行遍历一边，查找数组元素是否为6，若是6，则将数组元素改写为2
查找某元素属于哪个集合

findl(x)
{
	return set[x];
}

  

 

  
1
  
2
  
3
  
4
 

第二种方法：（树）

合并两个集合
直接将领导a归附于领导b即可

merge2(a,b)
{
	set[a]=b;
}

  

 

  
1
  
2
  
3
  
4
 

查找某元素属于哪个集合（效率不高）

find2(x)
{
	r=x;
	while(set[r]!=r)
	{
		r=set[r];
		return r;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

优化后的算法：
查找：
解释：每个集合中最小的为树的根，每个节点的父节点是领导（不是最高领导，只是直属领导）

find2(x)
{
	r=x;
	while(set[r]!=r)
	{
		r=set[r];
		return r;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

合并：

merge3(a,b)
{
	if(height(a)==height(b))
	{
		height(a)==height(a)+1;
		set[b]=a;
	}else if(height(a)<height(b))
	{
		set[a]=b;
	}else 
	{
		set[b]=a;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

解释：树高的做领导，方框格格里面的（数组元素）用于装着领导

文章来源: blog.csdn.net，作者：花花叔叔，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_52077949/article/details/114536182