BFS

// C++ program to print connected components in
// an undirected graph
#include<iostream>
#include <list>
using namespace std;
#define ver 100005
// Graph class represents a undirected graph
// using adjacency list representation
class Graph
{
    int V; // No. of vertices

    // Pointer to an array containing adjacency lists
    list<int> *adj;

    // A function used by DFS
public:
    Graph(int V); // Constructor
  void BFS(int v, bool visited[]);
    void addEdge(int v, int w);
    void connectedComponents();
};

// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    int cnt=0;
    for(int v = 0; v < V; v++)
        visited[v] = false;

    for (int v=0; v<V; v++)
    {
        if (visited[v] == false and adj[v].size()!=0)
        {
            // print all reachable vertices
            // from v
            BFS(v, visited);
            cnt++;
            cout << "\n";
        }
    }
  cout<<cnt<<endl;
}
void Graph::BFS(int v, bool visited[])
{
  list<int> queue;
  visited[v] = true;
  queue.push_back(v);
  list<int>::iterator i;
  while (!queue.empty()) {
    v = queue.front();
    cout<<v<<" ";
    queue.pop_front();
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
      if (!visited[*i]) {
        visited[*i] = true;
        queue.push_back(*i);
      }
    }
  }
}


Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

// Drive program to test above
int main()
{
    // Create a graph given in the above diagram
    Graph g(ver); // 5 vertices numbered from 0 to 4
    g.addEdge(1, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    cout << "Following are connected components \n";
    g.connectedComponents();

    return 0;
}