并查集

介绍

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
顾名思义，并查集支持两种操作：

合并（Union）：合并两个元素所属集合（合并对应的树）

查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

算法示例

1. 原始并查集

class Disjointset{
	public: 
		Disjointset(int n):parent(n+1){
			for(int i=1;i<=n;++i){
				parent[i] = i;
			}
		}
		int Find(int index){
			return parent[index]==index?parent[index] : Find(parent[index]);
		}
		void Union(int index1,int index2){
			int pa = Find(index1);
			int pb = Find(index2); 
			if(pa!=pb){
				parent[pa] = pb;
			}
		}
	private:
		std::vector<int>parent;
};

2. 路径压缩

将节点的父节点设置为原树的根节点

int Find(int index){
    return parent[index]==index?parent[index] : parent[index] = Find(parent[index]);
}

3. 按秩合并优化后的并查集

class Disjointset{
	public: 
		Disjointset(int n):parent(n+1),h(n+1){
			for(int i=1;i<=n;++i){
				parent[i] = i;
				h[i] = 0;
			}
		}
		int Find(int index){
			return parent[index]==index?parent[index] : parent[index] = Find(parent[index]);
		}
		void Union(int index1,int index2){
			int pa = Find(index1);
			int pb = Find(index2); 
			if(pa!=pb){         
				if(h[pa] < h[pb]){
					parent[pa] = pb;  //根据秩进行合并，小秩节点成为子节点
				}else{
					parent[pb] = pa;
					if(h[pa]==h[pb])++h[pa];  
                    //子节点多的节点秩大，最终保持各节点秩相对平均，即子节点数量相对平均，使得查询路径变短
				}
			}
		}
	private:
		std::vector<int>parent;
		std::vector<int>h;
};

---

算法分析

1. 时间复杂度 $\alpha(n)$
2. 空间复杂度 $O(n)$

并查集时间复杂度参考OI Wiki-并查集复杂度

---

例题

1. leetcode 684.冗余连接