Skip to content

Instantly share code, notes, and snippets.

@chenyuxiang0425
Last active August 21, 2020 17:33
Show Gist options
  • Save chenyuxiang0425/92849e084fe7461c8f79fcf2d1ff5ad9 to your computer and use it in GitHub Desktop.
Save chenyuxiang0425/92849e084fe7461c8f79fcf2d1ff5ad9 to your computer and use it in GitHub Desktop.
并查集 Union-Find
import java.util.Arrays;
public class UnionFind {
private int[] intSet;
/* Creates a UnionFind data structure holding n vertices. Initially, all
vertices are in disjoint sets. */
public UnionFind(int n) {
intSet = new int[n];
Arrays.fill(intSet, -1);
}
/* Throws an exception if v1 is not a valid index. */
private void validate(int vertex) {
if (vertex < 0 || vertex >= intSet.length) {
throw new ArrayIndexOutOfBoundsException("Invalid index");
}
}
/* Returns the size of the set v1 belongs to. */
public int sizeOf(int v1) {
validate(v1);
int root = find(v1);
return -parent(root);
}
/* Returns the parent of v1. If v1 is the root of a tree, returns the
negative size of the tree for which v1 is the root. */
public int parent(int v1) {
validate(v1);
return intSet[v1];
}
/* Returns true if nodes v1 and v2 are connected. */
public boolean connected(int v1, int v2) {
validate(v1);
validate(v2);
return find(v1) == find(v2);
}
/* Connects two elements v1 and v2 together. v1 and v2 can be any valid
elements, and a union-by-size heuristic is used. If the sizes of the sets
are equal, tie break by connecting v1's root to v2's root. Unioning a
vertex with itself or vertices that are already connected should not
change the sets but may alter the internal structure of the data. */
public void union(int v1, int v2) {
validate(v1);
validate(v2);
int v1Size = sizeOf(v1);
int v2Size = sizeOf(v2);
int v1Root = find(v1);
int v2Root = find(v2);
if (connected(v1,v2)) {
return;
}
if (v1Size > v2Size) {
intSet[v1Root] -= sizeOf(v2Root);
intSet[v2Root] = v1Root;
} else {
intSet[v2Root] -= sizeOf(v1Root);
intSet[v1Root] = v2Root;
}
}
/* Returns the root of the set V belongs to. Path-compression is employed
allowing for fast search-time. */
public int find(int vertex) {
validate(vertex);
int root = vertex;
// find the index of the root
while (parent(root) >= 0) {
root = parent(root);
}
// path-compression
int currParent;
while (vertex != root) {
currParent = parent(vertex);
intSet[vertex] = root;
vertex = currParent;
}
return root;
}
}

union-find api

  • UF(int N)
  • void union(int p, int q)
  • int find(int p)
  • boolean connected(int p, int q)
  • int count()

实现方法

  • Quick-find
    • find 时 p = q 则可以
    • union 时把所有 = p 的变成 = q 的
  • Quick-union
    • find 时找根节点,根节点 p == id[p],如果不等则 p = id[p] 直到找到根
    • union 时候先找 p,q 的根,如果不等则 p 的根的 id 为 q 的根,也就是把 p 子树接在 q子树上 id[pRoot] = qRoot;
  • 加权 Quick-union
    • 这是为了实现每次都能小树接在大树上
    • 在要个数组 sz,用于储存每个根节点对应的分量的大小(也就是节点数),初始化时全为 1
    • find 不变
    • union 中 ,i、j为p、q的根节点,判断sz[i] 和 sz[j] 的大小,如果小于,则说明 i 树比 j 树小,i 接在 j 上 (id[i] = j),调整根的分量 (sz[j] += sz[i])
  • 路径压缩加权 Quick-union
    • find 时把所有路上遇到节点直接链接到根节点
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment