[1][Algorithm] Union-Find 并查集

Outline

• dynamic connectivity
• quick find
• quick union
• implementations
• applications

Dynamic connectivity

1. Union command
2. Find/connected query(yes/no)

• connected component

Quick Find[eager approach]

public class QuickFindUF {
    private int[] id;
    
    // O(N)
    public QuickFindUF(int x) {
        id = new int[N];
        for (int i=0; i<x; i++) {
            id[i] = i;
        }
    }

    // O(N)
    public void Union(int p, int q) {
        if (!FindQuery(p, q)) {
            int idp = id[p];
            id[p] = id[q];

            for (int i=0; id<id.length; i++) {
                if (id[i] == idp) {
                    id[i] = id[q];
                }                
            }
        }
    }

    // O(1)
    public boolean FindQuery(int p, int q) {
        return id[p] ==id[q];
    }
}

Quick Union[lazy approach]

public class QuickUnion {
    // id[i] represents the root of i
    private int[] id;

    // O(N)
    public QuickUnion(int N) {
        id = new int[N];
        for (int i=0; i<N; i++) {
            id[i] = i;
        }
    }

    // O(N)
    public Union(int p, int q) {
        int rootp = root(p);
        int rootq = root(q);
        id[rootp] = rootq;
    }

    // worst case: O(N)
    private int root(int x) {
        while (id[x] != x) x = id[x];
        return x;
    }

    // O(N)
    public boolean Find(int p, int q) {
        return root(p) == root(q);
    }
}

Improvements

WeightedQU

    private int[] sz;

    // O(lgN)
    public Union(int p, int q) {
        int rootp = root(p);
        int rootq = root(q);
        if (sz[rootp] >= sz[rootq]) {
            id[rootq] = rootp;
            sz[rootp] += sz[rootq];
        } else {
            id[rootp] = rootq;
            sz[rootq] += sz[rootp];
        }        
    }

Path Compression

    // O(lgN)
    private int root(int x) {
        while (id[x] != x) {
            id[x] = id[id[x]];
            x = id[x];
        }
        return x;
    }

Cost

• Quick Find

1. Union too expensive.
2. Trees can be too fat.

• Quick Union

1. Find too expensive.
2. Trees can be too tall.