Number of Connected Components

Medium

Python

def count_components(n,edges):
    parent=list(range(n))
    def find(x):
        while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
        return x
    count=n
    for u,v in edges:
        pu,pv=find(u),find(v)
        if pu!=pv: parent[pu]=pv; count-=1
    return count

Java

public int countComponents(int n,int[][] edges){
    int[] parent=new int[n];
    for(int i=0;i<n;i++) parent[i]=i;
    int count=n;
    for(int[] e:edges){
        int pu=find(parent,e[0]),pv=find(parent,e[1]);
        if(pu!=pv){parent[pu]=pv;count--;}
    } return count;
}
int find(int[] parent,int x){
    while(parent[x]!=x){parent[x]=parent[parent[x]];x=parent[x];}
    return x;
}

Key Insight

Union-Find. Python list(range(n)) initializes nicely. Nested function captures parent.

Python → Java Differences

list(range(n)) vs new int[n] with loop
Nested function captures parent
Union-Find identical

Python

def count_components(n,edges):
    parent=list(range(n))
    def find(x):
        while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
        return x
    count=n
    for u,v in edges:
        pu,pv=find(u),find(v)
        if pu!=pv: parent[pu]=pv; count-=1
    return count

Java

public int countComponents(int n,int[][] edges){
    int[] parent=new int[n];
    for(int i=0;i<n;i++) parent[i]=i;
    int count=n;
    for(int[] e:edges){
        int pu=find(parent,e[0]),pv=find(parent,e[1]);
        if(pu!=pv){parent[pu]=pv;count--;}
    } return count;
}
int find(int[] parent,int x){
    while(parent[x]!=x){parent[x]=parent[parent[x]];x=parent[x];}
    return x;
}

Algorithm Steps

1. Initialize parent array
2. Union edges
3. Count distinct roots

← Previous All Graphs Next →