UnionFind solution in Java with UnionFind template


  • 1

    After I read some unionfind solutions in the discuss, I found these solution are highly abstarcted. It is some difficult for fresh programmers to understand the solutions. Thus I implement the UnionFind template in this question. It can re-used to any union find problem.
    Hope it helps.

    public class Solution {
        class UnionFind{
            private int count;
            private int[] id;
            public UnionFind(int n){
                this.count = 0;
                this.id = new int[n];
                for(int i = 0; i < n; i ++){
                    id[i] = i;
                    count ++;
                }
            }
            public int getCount(){ return this.count; }
            public boolean isConnected(int p, int q){
                return find(p) == find(q);
            }
            public int find(int p){
                while(p != id[p]){
                    id[p] = id[id[p]];
                    p = id[p];
                }
                return p;
            }
            public void union(int p, int q){
                int i = find(p), j = find(q);
                if(i == j) return ;
                id[i] = j;
                count --;
            }
        }
        public int countComponents(int n, int[][] edges) {
            UnionFind unionfind = new UnionFind(n);
            for(int[] edge : edges){
                int s = edge[0], e = edge[1];
                unionfind.union(s, e);
            }
            return unionfind.getCount();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.