Number of Connected Components in an Undirected Graph

Jyothi
1 min readApr 13, 2022

Problem statement:

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

This is another example of disjoint sets problem.

Very simple one. Number of components is the number of disjoint sets. Number of disjoint sets are the number root nodes in root array.

Below is my solution:

int find(int *rt, int x){
int rx = rt[x];
if (rx == x)
return x;
return rt[x] = find(rt, rx);
}
void unin_link(int *rt, int *rnk, int x, int y){
int rx = find(rt, x);
int ry = find(rt, y);
if (rx != ry){
if (rnk[rx] > rnk[ry]){
rt[ry] = rx;
}else if (rnk[ry] > rnk[rx]){
rt[rx] = ry;
}else {
rt[ry] = rx;
rnk[rx] +=1;
}
}
return;
}
int countComponents(int n, int** edges, int edgesSize, int* edgesColSize){
int rt[n], rnk[n];
int ii;
for (ii=0; ii<n; ii++){
rt[ii]=ii;
rnk[ii]=1;
}

for (ii=0; ii<edgesSize; ii++){
unin_link(rt, rnk, edges[ii][0], edges[ii][1]);
}

int res=0;
for (ii=0; ii<n; ii++){
if (rt[ii]==ii)
res++;
}
return res;
}

--

--