12. Union Find

并查集算法介绍

• 元素的归属find O(1)

• 集合的合并union O(1)

• 在线算法，stream of input

• 不支持delete

为什么用HashMap不用int[]?

• 虽然hashmap没有map array快

• 但如果输入的index差值太大的话，int[]比hashmap浪费更多空间

Number of Islands

• 经典的union find应用，因为要频繁更新状态

• 每次先add当前的index

• 然后逐步union邻居，在union函数里check邻居是否valid to union

• 注意unioin邻居之前先check boundary

public class Solution {
    private class UnionFind{
        private Map<Integer, Integer> father;//child->father, child is land, father is land
        private Map<Integer, Integer> size;//root-> count of island 
        private int cnt;
        public UnionFind(){
            father = new HashMap<>();
            size = new HashMap<>();
            cnt = 0;
        }
        private void add(Integer index){
            if(father.containsKey(index)){
                return;
            }
            father.put(index, index);
            size.put(index, 1);
            cnt++;
        }
        private Integer find(Integer index){
            if(!father.containsKey(index)) return null;
            Integer root = index;
            //find
            while(father.get(root) != root){
                root = father.get(root);
            }
            //compression
            while(index != root){
                father.put(index, root);
                Integer next = father.get(index);
                size.put(root, size.get(root) + 1);//update size
                index = next;
            }
            return root;
        }
        private void union(Integer p, Integer q){
            Integer pRoot = find(p);
            Integer qRoot = find(q);
            if(pRoot == null || qRoot == null) return;//either of them is water
            if(pRoot.equals(qRoot)) return;//already unioned

            int pSize = size.get(pRoot);
            int qSize = size.get(qRoot);
            if(pSize > qSize){
                father.put(qRoot, pRoot);//q->p
                size.put(pRoot, pSize + qSize);
            }else{
                father.put(pRoot, qRoot);
                size.put(qRoot, qSize + pSize);
                //size.put(pSize, 0);//no necessary
            }
            cnt--;
        }
        private int getCount(){
            return this.cnt;
        }
    }

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res= new ArrayList<>();
        if(m <= 0 || n <= 0 || positions == null || positions.length < 1 || positions[0].length < 1) return res;
        UnionFind islands = new UnionFind();
        for(int[] position : positions){
            int x = position[0];
            int y = position[1];
            int index = x * n + y;

            islands.add(index);

            int[] dx = {0,0,1,-1};
            int[] dy = {1,-1,0,0};
            for(int i = 0; i < 4; i++){
                int xx = x + dx[i];
                int yy= y + dy[i];
                if(xx < 0 || xx >= m || yy < 0 || yy >= n) continue;//check boundary
                int neighbor = xx * n + yy;
                islands.union(index, neighbor);
            }
            res.add(islands.getCount());
        }
        return res;
    }
}

Number of Connected Components

Longest Consecutive Sequence

• weightedUnionFind模板

• 注意corner case, num == Integer.MIN_VALUE, num == Integer.MAX_VALUE

• 还有hashset的巧妙做法

class Solution {
    public class UnionFind {
        Map<Integer, Integer> childToParent;
        Map<Integer, Integer> rootToSize;
        int maxSize;
        public UnionFind() {
            childToParent = new HashMap<>();
            rootToSize = new HashMap<>();
            maxSize = 1;
        }

        private void add(Integer num) {
            if (childToParent.containsKey(num)) return;
            childToParent.put(num, num);
            rootToSize.put(num, 1);
        }

        private int getMaxSize() {
            return this.maxSize;
        }

        private Integer findRoot(Integer num) {
            if (!childToParent.containsKey(num)) return null;
            Integer root = num;
            while (childToParent.get(root) != root) {
                root = childToParent.get(root);
            }
            //path compression
            while (childToParent.get(num) != root) {
                Integer parent = childToParent.get(num);
                childToParent.put(num, root);
                num = parent;
            }
            return root;
        }

        private void union(Integer p, Integer q) {
            Integer pRoot = findRoot(p);
            Integer qRoot = findRoot(q);
            if (pRoot == null || qRoot == null || pRoot.equals(qRoot)) return;
            Integer pSize = rootToSize.get(pRoot);
            Integer qSize = rootToSize.get(qRoot);
            if (pSize < qSize) {
                childToParent.put(pRoot, qRoot);
                rootToSize.put(qRoot, pSize + qSize);
            } else {
                childToParent.put(qRoot, pRoot);
                rootToSize.put(pRoot, pSize + qSize);
            }
            maxSize = Math.max(maxSize, pSize + qSize);
        }
    }
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        UnionFind uf = new UnionFind();
        for (int num : nums) {
            uf.add(num);
            //corner case
            if (num != Integer.MIN_VALUE) {
                uf.union(num, num - 1);
            }
            if (num != Integer.MAX_VALUE) {
                uf.union(num, num + 1);
            }
        }
        return uf.getMaxSize();
    }
}