Concise Java Union-Find with path compression

  • 11

    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]);
            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

    Good idea to count components with set. Thanks.

  • 0

    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.