Skip to content

Commit b71c822

Browse files
authored
Number of Components by Disjoint Set Algo
1 parent e290211 commit b71c822

File tree

1 file changed

+47
-0
lines changed

1 file changed

+47
-0
lines changed

Graphs/DSU.cpp

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
#include<stdio.h>
2+
#include<vector>
3+
using namespace std;
4+
int find(int* parent,int val) {
5+
if(parent[val]!=val)
6+
parent[val]=find(parent,parent[val]);//find the leader of the group of this node
7+
return parent[val];
8+
}
9+
10+
void unionSet(int* parent,int a,int b) {
11+
int ap = find(parent,a);
12+
int bp = find(parent,b);
13+
if(ap!=bp)
14+
parent[bp]=ap; //make 'a's parent as the leader of b's group as well.
15+
}
16+
int countNumberOfComponents(vector<vector<int>>& M) {
17+
int n = M.size();
18+
int parent[n]; //stores parent for each node
19+
for(int i=0;i<n;i++) parent[i]=i; //initially every node is individual
20+
for(int i=0;i<n;i++) {
21+
for(int j=i+1;j<n;j++) {
22+
if(M[i][j] && parent[i]!=parent[j]) {
23+
unionSet(parent,i,j); // if there is an edge, but parents are different that means these
24+
// two nodes(and hence the tress asociated with them) can be clubbed
25+
}
26+
}
27+
}
28+
//this now counts number of components.
29+
int count=0;
30+
for(int i=0;i<n;i++) {
31+
if(parent[i]==i) count++;
32+
}
33+
return count;
34+
}
35+
36+
int main() {
37+
int vertices,edges,from,to;
38+
scanf("%d%d",&vertices,&edges);
39+
vector<vector<int> > adjacencyMatrix(vertices, vector<int>(vertices,0));
40+
for(int i=0;i<edges;i++)
41+
{
42+
scanf("%d%d",&from,&to);
43+
adjacencyMatrix[from][to]=adjacencyMatrix[to][from]=1;
44+
}
45+
printf("%d",countNumberOfComponents(adjacencyMatrix));
46+
return 0;
47+
}

0 commit comments

Comments
 (0)