Concise Java Union-Find with path compression


  • 9
    Y

    The idea is very clear. Each node is in a set of size 1 initially. Every edge would connect 2 separate sets if the nodes the edge incident to are in different sets. After processing all nodes, we count the number of nodes whose root is itself.

    public class Solution {
    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]), root2 = findRoot(root, edge[1]);
            //Union
            if(root1 != root2) root[root2] = root1;
        }
        //Count components
        int count = 0;
        for(int i = 0; i < n; i++) if(root[i] == i) count++;
        return count;
    }
    
    //Find with path compression 
    private int findRoot(int[] root, int i){
        while(root[i] != i){
            root[i] = root[root[i]];
            i = root[i];
        }
        return i;
    }
    

    }


  • 0
    F

    Good idea to count components with set. Thanks.


  • 0
    P

    What would the time complexity be for this?


Log in to reply
 

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