dfs and bfs :D

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

typedef long long          ll;
typedef vector<int>        vi;
typedef pair<int, int>     ii;
typedef vector<ii>         vii;
typedef set<int>           si;
typedef map<string, int>   msi;

#define MAX 2000000000
//#define for(i, a, b) \
//  for(int i = int(a); i <= int(b); i++)
//#define Rvi(c, it) \
//  for(vi::iterator it = (c).begin(); it != (c).end(); it++)
//#define Rvii(c, it) \
//  for(vii::iterator it = (c).begin(); it != (c).end(); it++)
//#define Rmsi(c, it) \
//  for(msi::iterator it = (c).begin(); it != (c).end(); it++)

vector<bool> M;
vector<vi> G;

void dfs(int n) {
  cout << n << " ";

  M[n] = true;

  for(int i=0; i<G[n].size(); i++) {

    if(!M[G[n][i]]) {
      dfs(G[n][i]);      
    }

  }
}

int main() {
  
  int v, e;
  scanf("%d %d", &v, &e);
  M.assign(v+1, false);
  G.assign(v+1, vi());

  
  for(int i=0; i<e; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  //got the data!
  
  int components=0;
  for(int i=1; i<v+1; i++) {
    if(!M[i]) {
      components++;
      dfs(i);
    }
  }

  cout << endl;
  cout << "components: " << components << endl;
  //made deepth first search! and found how much components it has

  queue<int> Q;
  vi D(v+1, MAX), P(v+1, -1);
  Q.push(1);
  D[1] = 0;
  
  while(!Q.empty()) {
    int u = Q.front();
    cout << u << " ";
    Q.pop();
    
    for(int i=0; i<G[u].size(); i++) {
      if(D[G[u][i]] == MAX) {
	D[G[u][i]] = D[u] + 1;
	P[G[u][i]] = u;
	Q.push(G[u][i]);
      }
    }
  }
  cout << endl; //got D and P
  
  cout << "distance between 1 and 6: " << D[6] << endl;
  
  int i=6;
  while(i != -1) {
    cout << i << " <- ";
    i= P[i];
  }
  cout << endl; //got one of the shortest paths! 

  // BFS ... *-*
  // -> how do you find all of the shortest paths?

  return 0;
}