Similar to Number of Islands II, with a findRoot function

  • 6

    Use the similar method as Number of Islands II. Use a findRoot function. See more details in

    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;
        return res;
    public int findRoot(int[] root, int i) {
        while (root[i] != i) i = root[i];
        return i;

  • 0

    thx for sharing! very easy to understand!

  • 0

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

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


    a) update root along the way

                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.