Java 4ms DisjointSet Union-find w/ path compression


  • 0

    Disjoint sets are initialized such that every vertex belongs to a disjoint set. We traverse all edges. For each edge, we find the roots of them and check if they belong to the same disjoint set. If yes, it means a cycle these two vertices are of the same components so we do nothing. If no, we union them using path compression and they become the same components. In the end we count the number of remaining disjoint sets (array with negative value) and that's the number of components. Make sure you do the find before union because union takes only roots as arguments.

    Sorry for the incorrect indent. I used google docs to code and use tab to indent. Anyone knows how to adjust the length of tab indent? Some company use google docs to do phone interview and I find in order to make one character indent, we need to type 2 spaces. That's a lot of spaces. The tab length is too long and is not adjustable. Any good way to make indent quick and easy?

    public class Solution {
                public int countComponents(int n, int[][] edges) {
                if (n < 2 || edges == null || edges.length == 0)
                        return n;
                DisjointSets sets = new DisjointSets(n);
                int root1, root2, u, v;
                for (int i = 0; i < edges.length; i++) {
                u = edges[i][0];
                v = edges[i][1];
                root1 = sets.find(u);
                root2 = sets.find(v);
                if (root1 != root2)
                sets.union(root1, root2);
        }
        return sets.numOfSets();
        }
        }
        
        
        class DisjointSets {
                private int[] array;
                public DisjointSets(int n) {
                array = new int[n];
                for (int i = 0; i < n; i++)
                        array[i] = -1;
        }
        
        
        public int find(int x) {
                if (array[x] < 0)
                        return x;
                array[x] = find(array[x]);
                return array[x];
        }
        
        
        public void union(int root1, int root2) {
                if (array[root1] < array[root2]) {
                array[root1] += array[root2];
                array[root2] = root1;
        } else {
                array[root2] += array[root1];
                array[root1] = root2;
        }
        }
        
        
        public int numOfSets() {
                int count = 0;
                for (int i : array)
                        if (i < 0)
                                count++;
                        return count;
        }
        }

Log in to reply
 

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