*Java* Union find & path compression with brief comments


  • 0
    E
    public int countComponents(int n, int[][] edges) {
        if(n<1) return 0;
    	int[] size = new int[n]; // size of components at every node
    	int[] root = new int[n]; // root of current node
    	for(int i=0; i<n; i++) size[i] = 1; // initialize size to 1
    	for(int i=0; i<n; i++) root[i] = i; // initialize root to itself
    	for(int[] edge : edges) union(edge[0], edge[1], root, size); // union all edges
    	    
    	int count = 0;
        for(int i=0; i<n; i++) count += (root[i]==i) ? 1 : 0;
            
        return count;
    }
    
    private int root(int a, int[] root) {
    	while(a!=root[a]) a = root(root[a], root); // path compression
    	return a;
    }
    
    private void union(int a, int b, int[] root, int[] size) {
        int roota = root(a, root);
    	int rootb = root(b, root);
    	if(roota==rootb) return; // (a,b) already in same set, return immediately
    	if(size[roota]>size[rootb]) {
    		size[roota] += size[rootb]; // set larger size to sum
    		root[rootb] = roota; // set smaller node to larger node's child
    	}
    	else {
    		size[rootb] += size[roota];
    		root[roota] = rootb;
    	}
    }

Log in to reply
 

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