Basics

基本操作

• find: o(n), n is tree height
• compressed_find: O(1)
• union: o(1)
• optimization:
  • 按秩合并: ie 浅的合并到深的 rank
  • 加个 rank储存层数

class UnionFind {
    Map<Integer, Integer> father = new HashMap<>();

    UnionFind(Set<Integer> hashset) {
        for (Integer curr: hashset) {
            father.put(curr, curr)    
        }
    }

    // o(h), h is the tree height
    int find(int x) {
        int parent = father.get(x);
        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }

        return parent;
    }

    //refresh hashmap to 使得所有的leaf 都 point to root instead of father
    int compressedFind(int x) {
        int parent = father.get(x);
        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }

        int temp = -1;
        int fa = father.get(x);
        while (fa != father.get(fa)) {
            temp = father.get(fa);
            father.put(fa, parent);
            fa = temp;
        }
        return parent;
    }

    // o(1)
    void union(int x, int y) {
        int fa_x = compressedFind(x);
        int fa_y = compressedFind(y);

        if (fa_x != fa_y) {
            father.put(fa_x, fa_y);
        }    
    }

    //////
    int compressedFind2(int x) {
        if (x != father[x]) {
            father[x] = compressedFind2(father[x]);
        }
        return father[x];
    }
}

class UnionFind {
int[] parent;
int[] rank;
int count;

UnionFind(int n) {
parent = new int[n];
rank = new int[n];
this.count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}

int find(int x) {
if (x == father[x]) { // NOTICE: **if** not **while**
return x;
}
return father[x] = find(father[x]); // find with path compression
}

void union(int x, int y) {
int X = find(x);
int Y = find(y);
if (rank[X] > rank[Y]) { parent[Y] = X; } // tree Y is lower
else if (rank[X] < rank[Y]) { parent[X] = Y; } // tree X is lower
else { // same height
parent[Y] = X;
rank[X]++;
}
count--;
}

int getCount() {return this.count;}
}

number of islands ii

graph valid tree (detect cycle)