并查集的用处 – 分组和查询分组
并查集可以快速地分组和查询分组，时间复杂度近似常数，通常用于解决图的 连通性 问题。分组时使用 并操作 将元素划为一组或加入同一个连通分量，查询组别或所属连通子图时 使用 查操作 返回组中
单节点 – 单节点连通性
通过分组将联通分量分为同一组
检测大型电路中两个点是否连通
检测网络中两个节点是否可达到
检测社交网络中两人是否有关系
多节点 – 多节点连通性
在多节点端外额外添加一个节点作为根节点
将多节点与根节点分为一组
遍历图将联通分量分为同一组
仅需检测两端额外添加的根节点是否同一组别
并查集的表示
abstract class UF { protected int id[]; // 组标识 protected int sz[]; // 元素数 protected int count; // 总组数 public abstract int find(int i); // 查操作 public abstract void union(int p, int p); // 并操作 public boolean connected(int p, int q) { // 判连接 return find(p) == find(q); } public UF(int N){ // 初始化为N个组别 count = N; id = new int[N]; sz = new int[N]; for(int i = 0; i < N; i++) { id[i] = i; sz[i] = 1; } } }
并查集的实现
快速查找 Quick Find – 新加节点id作为组标识
表示法 每个元素各自存储所属的组id，同一分组的组id相同
并操作 把容纳组节点存储的组标识一一修改为新加节点的id
查操作 读取元素存储的组标识id
复杂度 并操作\scriptsize O(n)，查操作\scriptsize O(1)
class QuickFindUF extends UF {
@Override
public int find(int i) {
return id[i];
}
@Override
public void union(int p, int q){
int pId = find(p);
int qId = find(q);
if(pId == qId) return;
for(int i = 0; i < id.length; i++)
if(id[i] == pId) id[i] = qId;
count--;
}
}快速合并 Quick Union – 根节点id作为组标识
表示法 仅用根节点id唯一标识组别，子节点链接根节点来读取标识
并操作 合并两节点实际是合并两个组，即将并入组根节点成为容纳组根节点的子树
查操作 根据链接查询至根节点，读取组标识id
复杂度 并查操作均为 \scriptsize O(height(tree))
class QuickUnionUF extends UF {
@Override
public int find(int i) {
if(i == id[i]) return i;
return find(id[i]);
}
@Override
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[qRoot] = pRoot;
count--;
}
}带权快速合并 Weighted Quick Union – 小树成子树
表示法 维护树的容量字段，让小规模树成为大规模树的子节点，防止树过高而降低查询链接速度
并操作 改进快速合并，将小树根节点成为大树根节点的子节点，同时修改树的大小
查操作 同快速合并，链接查询至根节点
复杂度 并查操作均 \scriptsize O(\log n)
class WeightedQuickUnionUF extends UF {
@Override
public int find(int i) {
if(i == id[i]) return i;
return find(id[i]);
}
@Override
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
if(sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else {
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
count--;
}
}路径压缩快速合并 Path Compression Quick Union – 直接挂树根
表示法 快速合并的改进。查操作检索根节点同时，将所有被检索节点指向根节点，减小树高度
并操作 同快速合并
查操作 同快速合并，区别是向上检索节点时，将每个节点都指向根节点
复杂度 并查操作均接近 \scriptsize O(1)
class WeightedQuickUnionUF extends UF {
@Override
public int find(int i) {
if(i == id[i]) return i;
return id[i] = find(id[i]);
}
@Override
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[qRoot] = pRoot;
count--;
}
}路径压缩的带权快速合并 Weighted Path Compression Quick Union
结合带权和路径压缩两种优点，有效控制树的高度，从而并查操作性能逼近 \scriptsize O(1)
class WPCQuickUnion extends UF{
@Override
public int find(int i) {
if(i == id[i]) return i;
return id[i] = find(id[i]);
}
@Override
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
if (sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else {
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}应用案例
/**
* ---------------------------------------------------------------
* - 实现思路
* 己方和对方分为两组 -> 己方和对方的对方分为一组
* 使用路径压缩的带权快速合并
* - 实现细节
* 初始每个节点以id为组标识符自成一组，额外内存op保存节点的对方
* 依据对方节点的op查询己方节点分入己方组，op为0的节点还未分组
* 每次合并分组时将未分组节点划入已分组节点
* - 其他注意
* 输入数据从1开始，数组开为N+1尺寸方便操作
* 输入的两个数据均为己方时，造成数据矛盾
* ---------------------------------------------------------------
*/class UnionFind {
private int[] id;
private int[] op;
private int[] sz;
public UnionFind(int N) {
id = new int[N + 1];
op = new int[N + 1];
sz = new int[N + 1];
for (int i = 0; i <= N; i++) {
id[i] = i;
sz[i] = 1;
}
}
public int[] op(int i) {
return op;
}
// union方法、find方法见路径压缩的带权快速合并
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
UnionFind uf = new UnionFind(N);
while (sc.hasNext()) {
String flag = sc.next();
int p = sc.nextInt();
int q = sc.nextInt();
switch (flag) {
case "A":
if (uf.find(p) == uf.find(q))
System.out.println("In the same gang.");
else if (uf.find(p) == uf.find(uf.op[q]))
System.out.println("In different gangs.");
else
System.out.println("Not sure yet.");
break;
case "D":
if (uf.find(p) == uf.find(q))
throw new Exception("Ambiguous Data");
if (uf.op[p] == 0) {
if (uf.op[q] == 0) {
uf.op[p] = q;
uf.op[q] = p;
}
else {
uf.op[p] = q;
uf.union(p, uf.op[q]);
}
}
else {
if (uf.op[q] == 0) {
uf.op[q] = p;
uf.union(q, uf.op[p]);
}
else {
uf.union(p, uf.op[q]);
uf.union(q, uf.op[p]);
}
}
break;
default: throw new Exception("Non-Compliant Input");
}
}
}初始状态如下所示
id [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sz [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] op [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
新入节点1和节点2相互保存对方组别标识
> D 1 2
id [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sz [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] op [0, 2, 1, 0, 0, 0, 0, 0, 0, 0] ↑ ↑
新入节点4依据节点1查询到己方节点2并分为一组
> D 1 4
id [0, 1, 4, 3, 4, 5, 6, 7, 8, 9] sz [1, 1, 1, 1, 2, 1, 1, 1, 1, 1] op [0, 2, 1, 0, 1, 0, 0, 0, 0, 0] ↑ ↑ ↑