Union-Find & 2D matrix

Key points

• 2D -> 1D, i*cols + j

• union find

implementation: http://blog.csdn.net/dm_vincent/article/details/7655764 https://leetcode.com/problems/surrounded-regions/description/ https://leetcode.com/problems/number-of-islands/ https://leetcode.com/problems/number-of-islands-ii/description/

dummy node:

• https://leetcode.com/problems/surrounded-regions/description/

• https://leetcode.com/problems/bricks-falling-when-hit/discuss/121077/Java-Union-Find-by-backwardly-adding-bricks-back-20ms

Template

Example: https://leetcode.com/problems/graph-valid-tree/description/

class Solution {
    public boolean validTree(int n, int[][] edges) {
        UF uf = new UF(n);
        for (int i = 0; i < edges.length; i++) {
            if (uf.connected(edges[i][0],edges[i][1])) return false; // A cycle
            uf.union(edges[i][0],edges[i][1]);
        }
        return edges.length == n - 1;
    }
}

class UF {
    int[] father;
    int count;
    // All other parts are the same.
    // The difference is how to initialize UF.
    public UF(int n) {
        father = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }
    public void union(int p, int q) {
        int pFather = find(p);
        int qFather = find(q);
        if (pFather != qFather) {
            father[pFather] = qFather;
            count--;
        }
    }
    public int find(int p) {
        while (p != father[p]) p = father[p];
        return p;
    }
    public int count() {
        return count;
    }
    public boolean connected(int p, int q) {
        return find(p) == find (q);
    }
}

Optimized: path compression, union by size weight.

class UF {
    int[] father;
    int[] size;
    int count;
    // All other parts are the same.
    // The difference is how to initialize UF.
    public UF(int n) {
        count = n;
        father = new int[n];
        for (int i = 0; i < n; i++) father[i] = i;
        size = new int[n];
        for (int i = 0; i < n; i++) size[i] = 1;
    }
    public void union(int p, int q) {
        int pFather = find(p);
        int qFather = find(q);
        if (pFather == qFather) return;
        if (size[p] > size[q]) {
            father[qFather] = pFather;
        } else {
            father[pFather] = qFather;
        }
        count--;
    }

    // Path compression
    public int find(int p) {
        if (p != father[p]) {
            father[p] = find(father[p]);
        }
        return father[p];
    }
    public int count() {
        return count;
    }
    public boolean connected(int p, int q) {
        return find(p) == find (q);
    }
}

String version

Use map to represent fathers.

• 734-Sentence Similarity

• https://leetcode.com/problems/accounts-merge/description/

class UnionFind {
    Map<String, String> fathers = new HashMap<>();
    void connect(String s1, String s2) {
        fathers.putIfAbsent(s1, s1);
        fathers.putIfAbsent(s2, s2);

        String f1 = find(s1);
        String f2 = find(s2);
        if (!f1.equals(f2)) fathers.put(f1, f2);
    }
    String find(String s) {
        if (!fathers.get(s).equals(s)) {
            fathers.put(s, find(fathers.get(s)));
        }
        return fathers.get(s);
    }
}

Detect cycle

Union the edges. If two vertex are already connected, then current edge will form a cycle.

• 684-Rredundant C-connection

• 685-Redundant Connection II

Path finding

Node A, B connected: there is a path from A to B.

• 778. Swim in Rising Water