Union-Find

模板

    // 实现一个基于hashmap 的并查集
class UnionFind {
    HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
    public UnionFind(HashSet<Integer> hashSet) {
        // init
        for (Integer now : hashSet) {
            father.put(now, now);
        }
    }

    public int find(int x) {
        int parent = father.get(x);
        // must be use while-loop!!!
        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }
        return parent;
    }

    // 路径压缩
    public int compressed_find(int x) {
        int parent = father.get(x);
        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }
        int next;
        while (x != father.get(x)) {
            next = father.get(x);
            father.put(x, parent);
            x = next;
        }
        return parent;
    }

    public void union(int x, int y) {
        int fa_x = find(x);
        int fa_y = find(y);
        if (fa_x != fa_y)
            father.put(fa_x, fa_y);
    }
}

// 实现一个array的并查集
class UnionFind {
    int count;
    int[] table;

    UnionFind(int n) {
        table = new int[n];
        count = n;

        for(int i = 0; i < n; i++) {
            table[i] = i;
        }
    }

    public int find(int x) {
        return table[x];
    }

    public void union(int i1, int i2) {
        int f1 = table[i1];
        int f2 = table[i2];

        if(f1 != f2) {
            for(int i = 0; i < table.length; i++) {
                if(table[i] == f2) {
                    table[i] = f1;
                }
            }
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

Q&A

问: 面试中会碰到只有有并查集才能快速解的问题吗

答复: 有，比如http://www.lintcode.com/en/problem/number-of-islands-ii/ islands 2 应该很多同学在G家被面到过复:

听众问题

问: 为什么要用hashmap，而不用其他的东西？

答复: 也可以用数组，如果你知道数据的范围的话。

问: 这个查早怎么能是O（1） 呢？ 有while循环

答复: 单词操作的复杂度不会是O(1), 但是我们有路径压缩，长度为n的路径，一旦压缩以后，每个节点找到老大哥的复杂度都是O(1), 这里的复杂度O(1)是平均操作复杂度，在一些书上称均摊复杂度或者叫做 摊还复杂度

听众问题

问: 请分析三种解法的时间空间复杂度

答复: 三种方法的时间复杂度都是O(N)的，dfs和bfs 每个节点只属于一个连通块，所以每个节点只访问一次, 每条边链接两个点，所以每条边访问两次，复杂度是O(N+M).

听众问题

问: size怎么看呢？

答复: 我们每个集合有一个老大哥A，那么你可以用一个数据结构记录 Hash[A] 表示 A作为老大哥的节点所在集合的size ，A和B所在集合合并的时候 就是Hash[新的老大哥] = Hash[A的老大哥] + Hash[B的老大哥]

问: 如果fa_a == fa_b，那么合并这两个点，还是自己指向自己吧？有必要做最后一个判断么？

答复: 如果A的老大哥 和 B的老大哥是一样的，说明他们属于同一个集合 这时候是不需要合并的

听众问题

问: 有環怎麼判斷? 沒聽清楚

答复: 如果A的老大哥和B的老大哥一样了，那么此时已经是同一个集合（同一个连通块了），那么我们就不需要再去合并了。

听众问题

问: 代码里面怎么判断A和B在一个集合， 用BFS吗

答复: A的老大哥 等于 B的老大哥 就是在同一个集合内

听众问题

问: 有环~能在说下吗？

答复: 有环说明判断的时候两个点已经在同一个连通块内，已经属于同一个集合，此时两个点的老大哥一定是一样了的，所以不需要合并了（已经在同一个集合内了）

听众问题

听众问题

问: union操作怎么实现的

答复: union操作就是合并两个老大哥，大家应该看到 老大哥是没有父节点的（他是root 节点），A是老大哥，B是老大哥，合并他们所在的结合，可以把A的father指向B，这样B成了合并后的老大哥了

问: 老师，想再请问一下这个题的follow up，如果可能海水淹了现有的岛屿，该怎么做

答复: 就是有undo操作，一些公司可能问过，按原来添加的顺序反方向撤销操作，可以用stack保存结果就可以了。如果是随意删除岛屿就不能用并查集了，因为并查集不支持这种操作。没有好的解决方案