并查集 Union-Find
1.动态连通性 Dynamic connectivity
输入若干整数对，其中一对整数对p，q 可以理解为“p和q是相连的”。p q是对等关系，所以有下列性质：
- 自反性：p和q是相连的；
- 对称性：如果p和q是相连的，那么q和p也是相连的；
- 传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的。
若干整数对里面，只有两个对象相连时，才属于同一个等价类。我们的目标是编写程序来过滤掉序列中所有无意义的整数对（两个整数均来自同一个等价类中）。为了达到期望的效果，我们需要设计一个数据结构来保存已知的所有整数对的足够多的信息，同时可以使用它们判断是否连通。将这类问题统称为动态连通性问题。
Union-find data type (API)
pubic class UF
UF(int N) - initialize union-find data structure with N objects(0 - N - 1)
void union(int p, int q) - add connection between p and q
boolean connected(int p, int q) - are p and q in the sanme component?
int find(int p) - component indentifier for p (0 - N - 1)
int count() - number of components
模板如下：
public class UF {
private int[] id; // 分量id
private int count; // 分量数量
/**
* intialize
* @param N 分量数
*/
public UF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/**
* 后面不同的算法会使用不同的查找方式和连通方式
*/
public int find(int p) {}
public void union(int p, int q) {}
}
Dynamic-connectivity client
public class DynamicConnectivityClient {
public static void main(String[] args) {
int N = StdIn.readInt();
UF uf = new UF(N); // initialize
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (!uf.connected(p, q)) {
uf.union(p, q);
StdOut.println(p + " " + q);
}
}
}
}
2. 快速查找 Quick find
快速查找可以使查找时间复杂度降到O(1)常数级。
使用数组int[N] id，来记录两个触点是否存在于同一个连通分量中。
相同的id值说明是同一连通分量。
public class QuickFindUF {
private int[] id;
private int count; // 分量数量
public QuickFindUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// 查找p的值
public int find(int p) {
return id[p];
}
public void union(int p, int q) {
int pId = find(p);
int qId = find(q);
for (int i = 0; i < id.length; i++) {
if (id[i] == pId) id[i] = qId;
}
count--;
}
}
时间复杂度
-
find()-O(1) -
union()-O(N)
3. 快速合并 Quick Union
快速合并，采用“树”的思想，连通分量都在同一棵树上。
这样判断是否是在同一个连通分量，只需要看它们的根节点是不是一样的。
而union() 操作只需要将待连接节点的根节点与另一棵树的根节点连接即可。
public class QuickUnionUF {
private int[] id;
private int count;
public QuickUnionUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// 找到p的根节点。根节点是自己 本身
public int find(int p) {
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}
时间复杂度
-
find()操作的时间复杂度最坏情况下为O(N)。 -
union()操作的时间复杂度最坏情况下为O(1)。
4. 带权重的快速合并 Weighted Quick Union
上面的Qick-find算法，会出现一种最糟糕的情况，在连通的过程中，最终形成的树非常高，导致union() 操作的时间复杂度从常数级退化到O(n) ，效果非常差，find() 也是O(n) 。
所以我们在合并树的过程中，要权衡两棵树的深度，这里在数据结构中添加一个数组size[N] ，记录以当前下标节点为根节点的树，所包含的节点总数。
在进行union() 操作时，应该比较权值，然后让权重大的树作为根节点，让权重小的树接上去。由此，得到的新树就可以确保高度较小。
注：以上比较的两节点，都是待连通节点的根节点。
public class WeightedQuickUnionUF {
private int[] id;
private int[] size; // 权重，以当前下标为根节点的树的权重（节点总数）
private int count;
public WeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1; // 刚开始自己作为根节点，权值只有1
}
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
// 权重小的树接在权重大的树上
if (size[pRoot] < size[qRoot]) {
id[pRoot] = qRoot;
size[qRoot] += size[pRoot];
} else {
id[qRoot] = pRoot;
size[pRoot] += size[qRoot];
}
count--;
}
}
时间复杂度分析
-
find()操作的时间复杂度最坏情况下为O(lgN)。
原因在于我们每次都将包含对象较少的连通集连接到包含对象较大的连通集上，因此产生的连通集在最坏情况下的高度为O(lgN)。 -
union()操作的时间复杂度最坏情况下为O(lgN)。
原因与find()相同。
5. Quick-Union with path compression
在普通的Quick-Union基础上，查找根节点find() 过程中，每次循环是找到父节点，直到找到根节点，在每次循环中，把子树直接与根节点连接，让下面的子树深度降低，使整棵树的高度降低。
需要改变的只有find()
public class QuickUnionPathCompressionUF {
private int[] id;
private int count;
public QuickUnionPathCompressionUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
int root = p;
while (root != id[root]) root = id[root]; // 找到当前连通分量根节点
while (id[p] != root) {
int temp = p; // 保存当前位置
p = id[p]; // 将当前游标指向父节点
id[temp] = root; // 底下的子节点直接指向根节点，路劲压缩
}
return root;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}
6. 带权重的快速合并 带 路径压缩 Weighted Quick-Union with path compresson
思路同上，也是只改变find() 其余的不做调整。
public class WeightedQuickUnionByHeightUF {
private int[] id;
private int[] size;
private int count;
public WeightedQuickUnionByHeightUF(int N) {
count = N;
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
int root = p;
while (root != id[root]) root = id[root]; // 找到根节点
while (id[p] != root) {
int temp = p; // 同理，游标上移，子树直接连根节点
p = id[p];
id[temp] = root;
}
return root;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
if (size[pRoot] < size[qRoot]) {
id[pRoot] = qRoot;
size[qRoot] += size[pRoot];
} else {
id[qRoot] = pRoot;
size[pRoot] += size[qRoot];
}
count--;
}
}
