并查集（Union-find Sets）：是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。
使用并查集时，首先会存在一组不相交的动态集合 S={
S1,S2,⋯,Sk}S={S1,S2,⋯,Sk}，一般都会使用一个整数表示集合中的一个元素。
每个集合可能包含一个或多个元素，并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的，具体选择哪个元素作为代表一般也是不关心的。我们关心的是，对于给定的元素，可以很快的找到这个元素所在的集合（的代表），以及合并两个元素所在的集合，而且这些操作的时间复杂度都是常数级的。
并查集的基本操作有三个：
1.makeSet(s)：建立一个新的并查集，其中包含 s 个单元素集合。
2.unionSet(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交则不合并。
3.find(x)：找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
－对于并查集来说，每个集合用一棵树表示。
－集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。
－为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。
下面给出两种路径压缩方法：
递归式路径压缩：
const int MAXSIZE = 500010; int rank[MAXSIZE]; // 节点高度的上界 int parent[MAXSIZE]; // 根节点 int FindSet(int x){ // 查找+递归的路径压缩 if( x != parent[x] ) parent[x] = FindSet(parent[x]); return parent[x]; } void Union(int root1, int root2){ int x = FindSet(root1), y = FindSet(root2); if( x == y ) return ; if( rank[x] > rank[y] ) parent[y] = x; else{ parent[x] = y; if( rank[x] == rank[y] ) ++rank[y]; } } void Initi(void){ memset(rank, 0, sizeof(rank)); for( int i=0; i < MAXSIZE; ++i ) parent[i] = i; }
非递归式路径压缩：
const int MAXSIZE = 30001; int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目; //非根节点j,pre[j] = k,其中k是j的父节点 int Find(int x){ //查找+非递归的路径压缩 int p = x; while( pre[p] > 0 ) p = pre[p]; while( x != p ){ int temp = pre[x]; pre[x] = p; x = temp; } return x; } void Union(int r1, int r2){ int a = Find(r1); int b = Find(r2); if( a == b ) return ; //加权规则合并 if( pre[a] < pre[b] ){ pre[a] += pre[b]; pre[b] = a; } else { pre[b] += pre[a]; pre[a] = b; } } void Initi(void) { for( int i=0; i < N; ++i ) pre[i] = -1; }
转载于:https://www.cnblogs.com/darklights/p/5302659.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109115.html原文链接：https://javaforall.net
