Skip to content

Disjoint Sets

A disjoint-set data structure maintains a collections \(\delta = S_1, S_2, ..., S_k\) of disjoint dynamic sets. To identify each set, choose a representative, which is some member of the set. In some applications, it doesn't matter which member is used as the representative; it matters only that if you ask for the representative of a dynamic set twice without modifying the set between the requests, you get the same answer both times. Other applications may require a prespeciûed rule for choosing the representative, such as choosing the smallest member in the set (for a set whose elements can be ordered).

disjoint has no elements in common (不交集)

Screenshot 2024-09-12 at 18.50.46

Union-Find, also known as Disjoint Set Union (DSU), is a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets.

Find: Determine which subset a particular element belongs to. This can be used to check if two elements are in the same subset.

Union: Merge two subsets into a single subset.

root根节点

graph TD;
1 --- 2;
2 --- 3;
2 --- 4;

5 --- 6;
5 --- 7;
7 --- 8;

union: 合并两个元素为同一个根节点

Find: 找到某个元素的根节点, find(x);

find(8) = 5

union:

union(x, y);

graph TD;
1 --- 2;
2 --- 3;
2 --- 4;

5 --- 6;
5 --- 7;
7 --- 8;
1 --- 5;

Life Example:

graph TD;
A(A司令) --- B(a团长)
A --- C(c团长)
B --- 1
B --- 2
B --- 3
C --- 4 
C --- 5
C --- 6

D(B司令) --- E(b团长)
E --- 7
E --- 8
E --- 9

union:

graph TD;
A(A司令) --- B(a团长)
A --- C(c团长)
B --- 1
B --- 2
B --- 3
C --- 4 
C --- 5
C --- 6
A --- D
D(B司令) --- E(b团长)
E --- 7
E --- 8
E --- 9

graph TD;
 0; 1; 2; 3; 4; 
 5; 6; 7; 8; 9;
 1 --- 2;
 3 --- 4;
 3 --- 8;
 4 --- 9;
 5 --- 6;

(1, 2) true

(0, 7) false

(8, 9) true

Family?

graph TD;
 0; 1; 2; 3; 4; 
 5; 6; 7; 8; 9;
 0 --- 1;
 0 --- 5;
 1 --- 2;
 2 --- 7;
 3 --- 4;
 3 --- 8;
 4 --- 9;
 5 --- 6;

(1, 2) true

(6, 7) true

(8, 9) true

How to write in code?

graph TD;
0;
1;
2;
3;
4;
5;

1 --- 2;
1 --- 4;
4 --- 3;

class UnionFind{
  private int[] root = null;

  public UnionFind(int row, int col){
    int size = row * col;
    root = new int[size];
    for (int i = 0; i < size; i++){
      root[i] = i;
    }
  }


  // Find the root of x
  public int find(int x){
    if (x == root[x]){
      return root[x];
    }

    return root[x];
  }

  // Union two elements into one root
  public void union(int x, int y){
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY){
      root[rootY] = rootX;
    }
  }
}

leetcode: 200

leetcode: 547

https://www.bilibili.com/video/BV1Q5411H7v5/?spm_id_from=333.337.search-card.all.click&vd_source=73e7d2c4251a7c9000b22d21b70f5635

Union Find Improvement

Quick Find

class UnionFind{
  private int[] root = null;

  public UnionFind(int row, int col){
    int size = row * col;
    root = new int[size];
    for (int i = 0; i < size; i++){
      root[i] = i;
    }
  }


  // Find the root of x
  public int find(int x){
    if (x == root[x]){
      return root[x];
    }

    return root[x] = find(root[x]); // quick find
  }

  // Union two elements into one root
  public void union(int x, int y){
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY){
      root[rootY] = rootX;
    }
  }
}

Quick Union (Weight)

思想： 防止树太高

graph TD;
1;2;3;4;5;6;
1 --- 2;
1 --- 3;
3 --- 4;
4 --- 5; 
5 --- 6;

A[1];B[2];C[3];D[4];E[5];F[6];

A --- B;
A --- C;
A --- D;
A --- E;
A --- F;

class UnionFind {
    private int[] root;
    private int[] rank;  // For union by rank

    // Constructor initializes the union-find structure with a given size
    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];  // Initialize the rank array
        for (int i = 0; i < size; i++) {
            root[i] = i;  // Each element is its own root initially
            rank[i] = 1;  // Initialize rank as 1 for all elements
        }
    }

    // Find the root of x with path compression
    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        // Path compression optimization
        root[x] = find(root[x]);
        return root[x];
    }

    // Union two elements into one set with union by rank
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // Union by rank optimization
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;  // Attach smaller rank tree under larger rank tree
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;  // Increment rank if both have the same rank
            }
        }
    }

    // Check if two elements are connected (in the same set)
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}