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

}