Union find template and notes

class UnionFind {
        int[] father;
        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }

        public int find(int n) {
            if (father[n] != n) father[n] = find(father[n]);
            return father[n];
        }

        public void union(int a, int b) {
            father[find(a)] = find(b);
        }

        public boolean query(int a, int b){
            return find(a) == find(b);
        }
    } 
1. 融合不同的component


2. 判断环


3. 判断是否在一个group里面


Union find实现的关键是找father

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array