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