Similar to Number of Islands II, with a findRoot function


  • 6
    B

    Use the similar method as Number of Islands II. Use a findRoot function. See more details in https://leetcode.com/discuss/69572/easiest-java-solution-with-explanations

    public int countComponents(int n, int[][] edges) {
        int res = n;
    
        int[] root = new int[n];
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        for (int[] pair : edges) {
            int rootX = findRoot(root, pair[0]);
            int rootY = findRoot(root, pair[1]);
            if (rootX != rootY) {
                root[rootY] = rootX;
                res--;
            }
        }
        return res;
    }
    public int findRoot(int[] root, int i) {
        while (root[i] != i) i = root[i];
        return i;
    }

  • 0
    G

    thx for sharing! very easy to understand!


  • 0
    H

    I tried to do the two thing in a single function called:

    bool findUnion(vector<int>& root, int u, int v)
    

    Also,

    a) update root along the way

            while(uRoot!=uvRoot){
                int temp = uRoot;
                uRoot = root[uRoot];
                root[temp] = uvRoot;
            }
    

    b) pick the shortest path to update

    int uvRoot = (uCount>vCount||(uCount==vCount&&u<v))?uRoot:vRoot;
    

    , which unfortunately does not improve much.


Log in to reply
 

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