并查集模板

在计算机科学中，并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

因为它支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于建立单元素集合。有了这些方法，许多经典的划分问题可以被解决。

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着。Find(x)返回x所属集合的代表，而Union使用两个集合的代表作为参数。

在ACM中

并查集一般用于对动态连通性的判断，主要应用于判断两个元素是否在同一个集合，两个点是否连通，变量名等同性以及间接好友的判断。同时并查集经常作为其他模板的一部分实现某些功能。
并查集常用于的题型为判断某两个元素是否属于同一个集合，判断图是否连通或是否有环，或配合其他算法如最小生成树Kruskal，与DP共同使用等。

C/C++的并查集实现

不带高度的并查集

  int par[N];

  void init(int n) {
      for (int i = 0; i <= n; par[i] = i++);
  }

  void unite(int x, int y) {
      par[find(y)] = find(x);
  }

  int find(int u) {
      return par[u] == u ? par[u] : par[u] = find(par[u]);
  }

带高度的并查集

int par[MAX_N];
int rank[MAX_N];

void init(int n){
	for(int i=0;i<n;par[i]=i++)
		rank[i]=0;
}

int find(int u){
	return par[u] == u ? par[u] : par[u] = find(par[u]);
}

void unite(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y) return ;
	if(rank[x]<rank[y])
		par[x]=y;
	else{
		par[y]=x;
		if(rank[x]==rank[y]) rank[x]++;
	}
}

相关并查集的ACM习题

poj 1611 The Suspects

poj 1182 食物链(并查集经典题目)

并查集的优化

路径压缩

寻找祖先时采用递归，但是一旦元素一多起来，或退化成一条链，每次GetFather都将会使用O(n)的复杂度，这显然不是我们想要的。

对此，我们必须要进行路径压缩，即我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。这就是路径压缩了。

Rank合并

合并时将元素所在深度低的集合合并到元素所在深度高的集合。

参考资料：维基 /《挑战程序设计竞赛》/《Hrbust ACM Book》

并查集 模板

并查集的优化

路径压缩

Rank合并

相关文章