解决动态连通性问题

并查集UnionFind
数据结构与算法（十二）并查集(Union Find)及时间复杂度分析

684. Redundant Connection

947. Most Stones Removed with Same Row or Column

class Solution {
    Map<Integer, Integer> map;
    int islands;
    public int removeStones(int[][] stones) {
        map = new HashMap<>();
        islands = 0;
        for (int[] cur : stones) {
            union(cur[0], cur[1] + 10000);
        }
        return stones.length - islands;
    }
    private void union(int x, int y) {
        int root_x = find(x), root_y = find(y);
        if (root_x != root_y) {
            map.put(root_x, root_y);
            islands--;
        }
    }
    private int find(int x) {
        if (!map.containsKey(x)) {
            map.put(x, x);
            islands++;
        }
        if (x != map.get(x)) {
            //x = find(map.get(x)); //这样就可以直接return x，因为我们改变了x
            //map.put是使用了memorization，速度由13ms提升至10ms
            map.put(x, find(map.get(x)));
        }
        //被put的x是我们要find的x，val是 key == val的root, 原始x没有改变，所有x != his val
        //return x 的root/id
        return map.get(x);
    }
}

959. Regions Cut By Slashes