Graph-Questions/findnoofconnectedcomponents.cpp at main · subhradeepnag/Graph-Questions · GitHub

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
#include<bits/stdc++.h>
using namespace std;

class Graph
{
    public:
        map<int,bool>visited;
        map<int,list<int>>adj;

        void addEdge(int v,int w);
        void DFSutil(int v);
        void DFS();
};

void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
}

void Graph::DFSutil(int v)
{
    visited[v] = true;
    // cout<<v<<" ";
    list<int>::iterator i;
    for(i=adj[v].begin();i!=adj[v].end();i++)
    {
        if(visited[*i] == false)
        {
            DFSutil(*i);
        }
    }
}

void Graph::DFS()
{
    int count = 0;
    for(auto i:adj)
    {
        if(visited[i.first] == false)
        {
            DFSutil(i.first);
            count++;

        }
    }
    cout<<count;
}

int main()
{
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(0, 9);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(9, 3);
    g.addEdge(5, 7);
    g.DFS();
}