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

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

    // A function used by DFS
public:
    Graph(int V); // Constructor
  void BFS(int v, bool visited[]);
   void addEdge(list <iPair> adj[], int u,
                                     int v, int wt);
    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 (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
      if (!visited[i->first]) {
        visited[i->first] = true;
        queue.push_back(i->first);
      }
    }
  }
}


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

// method to add an undirected edge
void Graph:: addEdge(list <iPair> *adj, int u,
                                     int v, int wt)
{
    adj[u].push_back(make_pair(v, wt));
    adj[v].push_back(make_pair(u, wt));
}

// Drive program to test above
int main()
{
    // Create a graph given in the above diagram
   int V = 9;
  Graph g(V);
    // making above shown graph
    g.addEdge(adj, 0, 1, 4);
    g.addEdge(adj, 0, 7, 8);
    g.addEdge(adj, 1, 2, 8);
    g.addEdge(adj, 1, 7, 11);
    g.addEdge(adj, 2, 3, 7);
    g.addEdge(adj, 2, 8, 2);
    g.addEdge(adj, 2, 5, 4);
    g.addEdge(adj, 3, 4, 9);
    g.addEdge(adj, 3, 5, 14);
    g.addEdge(adj, 4, 5, 10);
    g.addEdge(adj, 5, 6, 2);
    g.addEdge(adj, 6, 7, 1);
    g.addEdge(adj, 6, 8, 6);
    g.addEdge(adj, 7, 8, 7);
    cout << "Following are connected components \n";
    g.connectedComponents();
    return 0;
}