Java solution, Union Find


  • 30

    This is a typical Union Find problem. I abstracted it as a standalone class. Remember the template, you will be able to use it later.

    public class Solution {
        class UnionFind {
            private int count = 0;
            private int[] parent, rank;
            
            public UnionFind(int n) {
                count = n;
                parent = new int[n];
                rank = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }
            
            public int find(int p) {
            	while (p != parent[p]) {
                    parent[p] = parent[parent[p]];    // path compression by halving
                    p = parent[p];
                }
                return p;
            }
            
            public void union(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ) return;
                if (rank[rootQ] > rank[rootP]) {
                    parent[rootP] = rootQ;
                }
                else {
                    parent[rootQ] = rootP;
                    if (rank[rootP] == rank[rootQ]) {
                        rank[rootP]++;
                    }
                }
                count--;
            }
            
            public int count() {
                return count;
            }
        }
        
        public int findCircleNum(int[][] M) {
            int n = M.length;
            UnionFind uf = new UnionFind(n);
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (M[i][j] == 1) uf.union(i, j);
                }
            }
            return uf.count();
        }
    }
    

  • 0
    D
                if (rank[rootQ] > rank[rootP]) {
                    parent[rootP] = rootQ;
                }
                else {
                    parent[rootQ] = rootP;
                    if (rank[rootP] == rank[rootQ]) {
                        rank[rootP]++;
                    }
                }
    
    Could you explain this part ? @shawngao

  • 0

    @dreamer92 That code snippet is used to decide which node will be used as Parent during Union two sets.


  • 10

    This is a typical Union Find problem - a similar problem is Graph Valid Tree
    A bit advanced Union Find problems are Number of Islands II and Number of Connected Components

        public int findCircleNum(int[][] M) {
            int m = M.length, cnt = 0;
            int[] root = new int[m]; 
            for (int i = 0; i < m; i++) root[i] = i; 
            for (int i = 0; i < m; i++) 
                for (int j = i + 1; j < m; j++)
                    if (M[i][j] == 1) unionFind(root, i, j);
    
            for (int i = 0; i < m; i++)
                if (i == root[i]) cnt++;
            return cnt;
        }
        
        void unionFind (int[] root, int v1, int v2) {
            while (root[v1] != v1) v1 = root[v1]; //find v1's root
            while (root[v2] != v2) v2 = root[v2]; //find v2's root
            if (root[v1] != root[v2]) root[v2] = v1; //unite the 2 subtrees 
        }

  • 2
    W

    @zzhai

    I do not think it is necessary to count the root nodes after the union-find operations, you just need minus 1 when you do a union operation.

      public int findCircleNum(int[][] M) {
        int count = M.length, roots[] = IntStream.range(0, M.length).toArray();
        for (int i = 0; i < M.length; i++)
          for (int j = i + 1, rootI = getRoot(roots, i), rootJ; j < M.length; j++)
            if (M[i][j] == 1 && rootI != (rootJ = getRoot(roots, j))) {
              roots[rootJ] = rootI;
              count--;
            }
        return count;
      }
    
      public int getRoot(int[] roots, int leaf) {
        while (leaf != roots[leaf]) leaf = roots[leaf] = roots[roots[leaf]];
        return leaf;
      }

  • 2

    Share my Union-Find solution which is a little more concise in the "Find" and "Union" part

    public class Solution {
        static int[] father;
        public int findCircleNum(int[][] M) {
            //corner case
            if(M.length == 0 || M[0].length == 0) return 0;
    
            int m = M.length;
            father = new int[m];
            for(int i = 0; i < m; i++){
                father[i] = i;
            }
            int counter = m;//initial counter as m
    
            for(int i = 0; i < m ; i++){
                for(int j = i + 1; j < m; j++){
                    if(M[i][j] == 1){
                        //Only need to union when they are in different groups
                        int father1 = find(i);
                        int father2 = find(j);
                        if(father1 == father2) continue;
                        
                        union(i, j);
                        counter--;
                    }
                }
            }
    
            return counter;
        }
    
        private int find(int root){
            if(father[root] == root) return father[root];
    
            father[root] = find(father[root]);
            return father[root];
        }
    
        private void union(int root1, int root2){
            int father1 = find(root1);
            int father2 = find(root2);
    
            if(father1 != father2){
                father[father1] = father2;
            }
        }
    }
    

  • 1
    B

    Sorry, what is the rank used for?


  • 0
    K

    @shawngao Could you please explain why "rank" is being used in your code?


  • 4
    B

    @kaddusingh Hi I think I found the answer from the book "Introduction to Algorithms" "CLRS". Basically this will provide a clue when you try to union 2 sets. 1 shorter 1 longer and bigger. So when you union, you would just want to update as few as possible. So we can keep a rank record to help us decide who is the smaller one and who is the bigger one to save us some time.


  • 0
    D

    in this solution, since he iterates the points in ascending order and j is always greater or equals to i.
    It is not necessary to keep the rank.
    We can always just do parent[rootP] = rootQ;


  • 0
    X

    I don't think you need a extra "rank" array here, only a parent array is enough right?


  • 2

    @xinlin5 You can say that. Rank array is used to accelerate union operation. It's in the original template. http://algs4.cs.princeton.edu/15uf/UF.java.html


  • 0
    F

    Same idea. Just a little bit difference.

    class Solution {
        int[] father;
        public class UnionFind {
            public UnionFind(int n) {
                for (int i = 1; i <= n; i++) {
                    father[i] = i;
                }
            }
            
            public int find(int x) {
                if (father[x] == x) {
                    return x;
                }
                return father[x] = find(father[x]);
            }
            
            public boolean query (int a, int b) {
                int x = find(a);
                int y = find(b);
                return x == y;
            }
            
            public void union (int a, int b) {
                int x = find(a);
                int y = find(b);
                if(x != y) {
                    father[x] = y;
                }
            }
        }
        
        public int findCircleNum(int[][] M) {
            int n = M.length;
            father = new int[n + 1];
            UnionFind uf  = new UnionFind(n);
            int count = n;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if(M[i][j] == 1 && !uf.query(i, j)) {
                        count--;
                        uf.union(i,j);
                    }
                }
            }
            return count;
        }
    }
    

  • 0
    K

    Great Solution. For detailed understanding of this Algorithm, I found this YouTube Video Link very Helpful. https://www.youtube.com/watch?v=ID00PMy0-vE


  • 0
    H

    We don't need to call the find method every time for both row and column indexes (i and j). Instead, we only need to call the find method only once for row index (i) before the going to the loop of column index (j). But in this way, we need to update the find result of i every time after the union. To do this, we can let the union method to return the final root to update the i value.
    I also write the union find to weighted and path compression union find. The time complexity is O(n^2*logn).

        public int findCircleNum(int[][] M) {
            int m = M.length;
            if(m==0) return 0;
            
            int[] roots = new int[m];
            int[] sc = new int[m];
            for(int i=0;i<m;i++) roots[i]=i;
            Arrays.fill(sc,1);
            
            int count=m;
            for(int i=0;i<m;i++)
            {
                int x= find(roots,i);
                for(int j=i+1;j<m;j++)
                {
                    if(M[i][j]!=1) continue;
                    int y= find(roots,j);
                    if(x!=y)
                    {
                        count--;
                        x=union(roots,x,y,sc);
                    }
                }
            }
            return count;
        }
        
        public int find(int[] roots, int i) {
            while(roots[i]!=i)
            {
                roots[i]=roots[roots[i]];//path compression
                i=roots[i];
            }
            return i;
        }
        
        public int union(int[] roots, int x, int y, int[] sc) {
            if(sc[x]>sc[y])//weighted union
            {
                roots[y]=x;
                sc[x]+=sc[y];
                return x;
            }
            else
            {
                roots[x]=y;
                sc[y]+=sc[x];
                return y;
            }
        }
    

Log in to reply
 

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