-
Notifications
You must be signed in to change notification settings - Fork 0
/
Connected_Components_of_Graph.cpp
61 lines (51 loc) · 1.08 KB
/
Connected_Components_of_Graph.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
class Graph
{
int V;
list<int> *graph;
public:
Graph(int V)
{
this->V = V;
graph = new list<int>[V];
}
void addEdge(int v, int w)
{
graph[v].push_back(w);
graph[w].push_back(v);
}
void connectedComponents(int source, vector<int> &visited)
{
if(!visited[source])
{
cout<<source<<" ";
visited[source] = 1;
for(auto i: graph[source])
if(!visited[i])
Graph::connectedComponents(i, visited);
}
}
};
int main()
{
int v = 5;
Graph g(v);
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
int counter = 0;
vector<int> visited(v, 0);
cout << "Following are connected components : \n";
for (int i = 0; i < v; i++)
{
if (!visited[i])
{
g.connectedComponents(i, visited);
cout<<endl;
counter++;
}
}
cout << "\nTotal connected components are : " << counter;
return 0;
}