BFS_example

#include <iostream>
using namespace std;

const int MAXN = 100;
int used[MAXN+1],Q[MAXN],P[MAXN],G[MAXN][MAXN] = {0},N, b,e;

void make_empty(){b=0;e=-1;}

void push(int x){Q[++e]=x;}

int pop(){return Q[b++];}

bool emptyQ(){return b>e;}

void BFS(int r) {
  int  x,y,i; for(i=1;i<=N;i++) used[i]=0;
  make_empty();push(r);used[r]=1;P[r]=0;
  while(!emptyQ()) {
    x=pop();
    for(i=1;i<=G[x][0];i++) {
      y=G[x][i];
      if(!used[y]) {push(y);used[y]=1;P[y]=x;}
     }
  }
}


int main(){

    int x,y;

    while( cin >> x >> y ){
    G[x][++G[x][0]] = y;
    G[y][++G[y][0]] = x;
    }

    BFS(1);

    for(int i=1; i<=10; i++ ) cout << i << " " << P[i] << endl;
    /*for( int i=1; i<10; i++ ){
        for( int j=0; j<10; j++ ){
            cout << G[i][j] << "  ";
        }
        cout << endl;
    }*/

    return 0;
}