首页 > 代码库 > 并查集
并查集
当我们在讨论图的连通性时，有时候图的边权或者点权值并不一定需要，如果此时还要坚持用图的结构来保存，则效率显然不高，因此，在这里我们使用并查集就可以。
并查集是一种值考虑两个节点是否连通而不考虑他们如果连通以及连通的代价的结构，他实质上是数学上的集合思想在计算机算法中的应用。在该结构中，两个节点要么连通（说明在一个集合中），要么不连通（不在一个集合中）。在这个结构中，我们常做的操作主要是查询一个节点是否在某个集合中，或者将一个节点放入某个集合中，也即查询与合并，因此，该结构通常称为 union-find（并查集）。
并查集的操作过程：我们用数组来实现并查集，每个节点的序号作为数组下表，其所在的集合有一个作为代表的节点（有时根据树结构，称为根节点），某节点对应数组元素的值为代表节点则说明该节点在该集合中，（有些用链表实现的并查集，则其指针（指向父节点）指向代表节点则说明该节点在该集合中）。
1，初始状态，每一个节点看作是一个集合，在该集合中只有一个节点。其值为自己（或者指针指向自己。
1 void makeSet(int size) { 2 for(int i = 0; i < size; i++) 3 id[i] = i; 4 }
2，对应每一个边，其对应的节点在同一个集合，故应该合并。其做法是将其中一个集合的代表节点的值赋值为另一个集合的代表节点。（即一个树的根指向另一个树的根）
1 public void union(int p, int q) 2 { 3 int pRoot = find(p); 4 int qRoot = find(q); 5 if (pRoot == qRoot) 6 return; 7 id[pRoot] = qRoot; 8 }
由于并查集是树的应用，其对应的树在合并时可以考虑到原有大小，这样，我们便可以选择规模小的树根节点指向规模大的树的节点（一般选择根节点）。以使得树不至于太过畸形，相对平衡。此时我们可以用另外一个数组来表示每个集合的大小。其初始状态为每个集合大小均为1。
1 for(int i = 0; i < size; i++) 2 id[i] = i;
在合并时，将先进行规模的比较
1 public void union(int p, int q) 2 { 3 int i = find(p); 4 int j = find(q); 5 if (i == j) return; 6 if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } 7 else { id[j] = i; sz[i] += sz[j]; } 8 }
3，可以发现，在合并过程中要先检查两者是否在同一个集合，我们只对不在一个集合的进行合并。这就出现了查询操作。
1 private int find(int p) 2 { 3 while (p != id[p]) p = id[p]; 4 return p;5 }
在查找的代码中可以看到，如果树的规模很大，则在沿着树向上寻找根的过程会耗费很大的精力，此时我们应该考虑在查找过程中，将每个节点都指向根节点。
树结构，我们可以很显然的想到递归的定义这种查询
1 int find(int x) {2 if (x != id[x]) 3 id[x] = find(id[x]);4 return id[x];5 }
也可以使用非递归方式
1 int find(int x) { 2 int p = x, t; 3 while (id[p] != p) p = id[p]; 4 while (x != p) { 5 t = id[x]; 6 id[x] = p; 7 x = t; 8 } 9 return x; 10 }
并查集