并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合,并支持合并与查询两种操作的一种数据结构。

优秀博客链接：并查集的两种优化(按秩合并，路径压缩)

并查集特性

• 并查集是一个森林，pre[]存放父结点
• Find()操作——可以查询任一结点的根结点并返回、判断两个节点是否属于同一个集合（是否属于同一个根节点下）
• Merge()操作——实现两个不同集合的合并
  ——————————————代码————————————————

  int pre[100005];    //父亲
  void Init(int m)    //初始化，每个节点的根就是自身
  {
  	for(int i = 1; i <= m; ++i)
  	{
  		pre[i] = i;
  	}
  }
  int Find(int x)     //查询树根
  {
  	while(pre[x]!=x)
  	{
  		x = pre[x];
  	}
  	return x;
  }
  void Merge(int x, int y)    //合并x和y所属的集合
  {
  	pre[Find(x)] = pre[Find(y)];
  }

并查集优化

两种优化方式都是为了尽可能降低树的深度。

• 路径压缩
  Find()查询树根中让路径中的每个节点直接指向根结点
  pre[x]=pre[pre[x]];
• 按秩合并
  runk[]记录某节点的高度
  Merge()合并时让高度小的树合并到高度大的树
  ——————————————代码————————————————

  int pre[N];		//父亲 
  int runk[N];	//高度 
  int Find(int x)	//查询树根 
  {
  	while(pre[x]!=x)
  	{
  		pre[x]=pre[pre[x]];  //路径压缩 
  		x = pre[x];
  	}
  	return x;
  }
  void Merge(int x, int y)	//合并x和y所属的集合 
  {
  	int xe = Find(x);
  	int ye = Find(y);
  	if(xe!=ye)
  	{
  		if(runk[xe]>=runk[ye])
  		{
  			pre[ye] = xe;
  			runk[xe] = max(runk[xe], runk[ye]+1);
  		}
  		else 
  		{
  			pre[xe] = ye;
  			runk[ye] = max(runk[ye], runk[xe]+1);
  		}
  		
  	}
  }

例题·蓝桥

题目来源：合根植物
算法思想
直接返回不同的集合数
连根现象即通过Merge()令两个结点属于同一集合
于是初始化pre[i] = i然后该合并的合并
最后通过Find(i)==i来确定不同的集合数
——————————————完整代码————————————————

#include <iostream>
#include <string> 
using namespace std;
int pre[1000005];
void Init(int m)
{
	for(int i = 1; i <= m; ++i)
	{
		pre[i] = i;
	}
}
int Find(int x)
{
	while(pre[x]!=x)
	{
		x = pre[x];
	}
	return x;
}
void Merge(int x, int y)
{
	pre[Find(x)] = pre[Find(y)];
}
int main()
{
	int m, n, k;
	scanf("%d%d%d", &m, &n, &k);
	Init(m*n);
	int x, y, ans = 0;
	for(int i = 0; i < k; ++i)
	{
		scanf("%d%d", &x, &y);
		Merge(x, y);
	}
	for(int i = 1; i <= m*n; ++i)
	{
		if(Find(i) == i)
			++ans;
	}
	printf("%d\n", ans);
	
	return 0;
}