Maybe test case not strong enough?


  • 1
    E

    I tried with quick union, it still passed in 6ms. Maybe we need stronger test cases?

    Here is the Java code with quick union:

    public class Solution {
    public int countComponents(int n, int[][] edges) {
        if(n<1) return 0;
    	int[] root = new int[n];
    	for(int i=0; i<n; i++) root[i] = i;
    	for(int[] edge : edges) quickUnion(edge[0], edge[1], root);
    	    
    	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[a];
    	return a;
    }
    
    private void quickUnion(int a, int b, int[] root) {
        int roota = root(a, root);
    	int rootb = root(b, root);
    	root[rootb] = roota;
    }
    }

  • 0

    Yeah, I just got a really naive solution accepted (naive except for the unicode string optimization).


Log in to reply
 

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