Number of Connected Components in an Undirected Graph

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;
}

--

--

www.linkedin.com/in/jyothivs

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store