Java Compress Path, Union Find, 3ms ,better than 7ms


  • 0
    B
    public int countComponents(int n, int[][] edges) {
        int[] root = new int[n];
        for(int i = 0; i < n; i++) {
        	root[i] = i;
        }
        for(int[] edge : edges) {
        	int root1 = findRoot(root, edge[0]);
        	int root2 = findRoot(root, edge[1]);
        	//union
        	if(root1 != root2) {
        		root[root2] = root1;
        	}
        }
        //count
        int count = 0;
        for(int i = 0; i < n; i++) {
        	if(root[i] == i) {
        		count++;
        	}
        }
        return count;
    }
    private int findRoot(int[] root, int i) {
    	while(root[i] != i) {
    		//compress
    		root[i] = root[root[i]];
    		i = root[i];
    	}
    	return i;
    }

Log in to reply
 

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