并查集

并查集的概念

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合
• 查询（Find）：查询两个元素是否在同一个集合中

基础并查集的核心思想在于，用集合中的一个元素代表集合。 判断两个元素是否在同一集合，只需判断这两个元素所在集合的代表元素是否相同，相同则在一个集合。而若要合并两个集合，只需让其中一个集合的代表元素的父节点等于另一个集合的代表元素即可。代码模板如下：

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
		p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
	p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

基础并查集问题的变种

并查集存在两种变种：

1. 维护并查集的额外信息，如集合中的元素数量等。
2. 利用并查集的思想。并查集并不直接处理两个元素的关系，而是比较其它元素来间接推出这俩元素的关系。