Union Find

问题建模：

• 给出两个结点，判断它们是否连通，如果连通，不需要给出具体的路径 → Union Find
• 给出两个结点，判断它们是否连通，如果连通，需要给出具体的路径 → DFS

应用场景：图片中的pixel，网络中的电脑，社交网络中的朋友，芯片中的晶体管，数学集合中的元素……

操作：
Union并: 将两个对象合并入同一集合
Find查: 检查两个对象是否属于同一集合

Quick-find: id[i]表示i所属的集合

查：p,q是否属于同一集合，id[p]=id[q]?

public class UFQuickFind{
	private int[] id;
	public UFQuickFind(int N){ // O(N)
		id = new int[N];
		for(int i = 0; i < N; i++){ id[i] = i; } // 初始化：每个元素自成一个集合
	}
	public void union(int p, int q){ // O(N)
		for(int i = 0; i < N; i++){
			if(id[i] == id[p]){ id[i] = id[q]; } // 将集合id[p]里所有元素合并到集合id[q]里
		}
	}
	public boolean find(int p, int q){ // O(1)
		return id[p] == id[q];
	}
}

优点：find只需要O(1)

缺点：因为每个结点的集合编号是独立记录的，没有以更好的方式(ie.数据结构)组织起来，所以进行一次union操作需要遍历整个集合来找到要修改的结点

Quick-union: id[i]表示i的父结点

i的根结点是id[id[……id[i]]]

并：让p的根结点的父结点为q的根结点，id[pRoot] = qRoot

查：p和q是否有相同根结点，root(p) == root(q)?

public class UFQuickUnion{
	private int[] id;
	public UFQuickUnion(int N){ // 初始化O(N)
		id = new int[N];
		for(int i = 0; i < N; i++){ id[i] = i; }
	}
	public int root(int p){ // O(N)
		while(p != id[p]){ p = id[p]; }
		return p;
	}
	public void union(int p, int q){ // O(N)
		int pRoot = root(p);
		int qRoot = root(q);
		id[pRoot] = qRoot;
	}
	public boolean find(int p, int q){ // O(N)
		return root(p) == root(q);
	}
}

优点：将结点与集合的关系以树的形式表现出来

缺点：树这种数据结构很容易出现极端情况，因为在建树的过程中，树的最终形态严重依赖于输入数据本身的性质，比如数据是否排序，是否随机分布等等。比如在输入数据是有序的情况下，构造的BST会退化成一个链表。在Quick Union的union()中，id[pRoot] = qRoot是基于让p所在的树成为q所在树的子树而hardcoded的，从而实现两颗独立的树的融合。那么这样的约定是不是总是合理的呢？显然不是，比如p所在的树的规模比q所在的树的规模大的多时，p和q结合之后形成的树就是十分不和谐的一头轻一头重的”畸形树“了。

优化(加权&路径压缩)

• 优化1: weighted quick union

idea: 每次union将矮树连到高树下 → 记录树的高度sz，

public class WeightedQuickUnion{
	private int[] id, sz;
	public WeightedQuickUnion(int N){ // 初始化
		id = new int[N];
		for(int i = 0; i < N; i++){
			id[i] = i;
			sz[i] = 1;
		}
	}
	public void union(int p, int q){ // O(logN)：因为有结点数N的树，高度最多为logN
		int pRoot = root(p);
		int qRoot = root(q);
		if(pRoot == qRoot) return; // p,q高度相同
		if(sz[p] < sz[q]){ id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } // p比q矮，p的根节点等于q的根结点，更新q的根结点的高度
		else{ id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } // q比p矮，q的根节点等于p的根结点，更新p的根结点的高度
	}
	public boolean find(int p, int q){ // O(logN)：原因同上
		return root(p) == root(q);
	}
}

注意高矮的不同定义Union by size(根据结点数) 和 Union by height(根据树的高度)，但时复都是logN。右图为Quick Union与Weighted Quick Union的比较。右图还可以给我们一些启示，即对于Quick-Union算法而言，结点组织的理想情况应该是一颗十分扁平的树，所有的孩子结点应该都在height=1的地方，即所有的孩子都直接连接到根节点。这样的组织结构能够保证find操作的最高效率。

• 优化2: 路径压缩path compression

将结点p及其所有父结点连到p的根上

public int root(int p){
	while(p != id[p]){
		id[p] = id[id[p]]; // p的父结点等于p的父结点的父结点 -> 使得路径长度减半
		p = id[p];
	}
	return p;
}

总结

应用：Perlocation从顶部到底部渗透

白色可流通，黑色不可流通；导体可流通电，绝缘体不可流通电；社交网络中，一群组是否与另一群组相通

渗透的可能性与open site数在NxN grid中的概率有关，且此概率有阈值，小于该阈值几乎肯定不能渗透，大于该阈值几乎肯定能渗透。

如何知道是否渗透？假设top&bottom sites，判断top&bottom sites是否connected?

Leetcode

Union Find基本运用：
547: Friends Circle - Weighted Quick Union

323. Number of Connected Components in an Undirected Graph - Weighted + 路径压缩; 对于每条边，若已connect，continue; 若未connect，union()，n- -; 最后n即为集合总数
324. Graph Valid Tree - Weighted + 路径压缩; 对于每条边，若已connect，return false; 若未connect，union()，n- -; 最后若n等于1，return true; 否则，return false
325. Redundant Connection - Weighted + 路径压缩; 找到最后一条2个node已连接的边

Union Find变形运用：
685. Redundant Connection II

参考阅读

Section 1.4 and 1.5 in Algorithms, 4th edition.
https://blog.csdn.net/dm_vincent/article/details/7655764