Write a c++ program to check whether a given graph is connected or not using DFS method. A graph is said to be connected when there is a path between every pair of nodes. In a connected graph, there are no unreachable nodes. A graph that is not connected is called disconnected graph.

For example the below figure , the left side of graph is connected graph while the right side graph is disconnected graph.

## Check whether a given graph is connected or not

To check whether a give graph is connected or not is simple. Here is simple steps to check.

• Run dfs algorithm starting from any vertex. ( To know more about dfs visit at http://wikistack.com/a-recursive-implementation-of-dfs/)
• After finishing dfs , count the number of visited nodes.
• If count is equal to number of vertices in graph, graph is connected else
• Graph is disconnected.

Here is simple implementation of above logic, please write comments if there is any problem with the code.

```#include<iostream>
#include <list>
using namespace std;

class G
{
int v; // No. of nodes
// array for visited nodes
bool *visited;
public:
G (int v);
void add_edge (int u, int v);
void reset_visited_array();
void dfs (int v);
bool isConnected();
};

G::G (int v)
{
this->v = v;
adj_list = new list < int >[v];
visited = new bool[v];
}

void G::add_edge (int u, int v)
{
// graph is undirected
// (u)--------------(v)
}

void G::reset_visited_array()
{
for(int i=0;i<v;i++)
visited[i] = false;
}
// dfs function from vertex v.
void G::dfs (int v)
{
if (!visited[v])
// make v visited
visited[v] = true;

//cout << v << " ";

// find all adjacent nodes from vertex v
list < int >::iterator i;
{
// If an adjacent node is not visited
if (!visited[*i])
{
dfs (*i);
}

}
}

bool G::isConnected()
{
int count = 0;
// count visited vertex
for(int i=0; i < v; i++)
{
if( visited[i] ) // if node v is visited
count++;
}
// check wheter the visited nodes count is equal
// to the count of all nodes
if( count == v )
return true;
else
return false;
}

int main ()
{
// look the above graph there are six
// nodes, the node number is starting from number 1
// so we will create 6 adjacency list
G g (6);
// make graph

// reset visited array
// before starting dfs, make each visited false
g.reset_visited_array();

// run dfs on graph G from vertex 1
g.dfs(1);

if( g.isConnected() )
{
cout<<"The graph is connected \n";
}
else
{
cout<<"The graph is disconnected \n";
}

G g1 (6);

g1.reset_visited_array();
g1.dfs(1);

if( g1.isConnected() )
{
cout<<"The graph is connected \n";
}
else
{
cout<<"The graph is disconnected \n";
}

return 0;
}
```