9a_BFS

#include <iostream>
using namespace std;

const int MAXN = 1000;
int used[MAXN+1], Q[MAXN], P[MAXN], G[MAXN][MAXN], 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; cout<< y <<" ";}
     }
  }
}


int main(){

    int N;
    while( cin >> N ){
        int x,y;
        for( int i=0; i<N; i++ ){
            cin >> y >> x;
            G[x][++G[x][0]] = y;
            G[y][++G[y][0]] = x;
        }
        cout << 1 << " ";
        BFS(1);
        memset(used, 0, MAXN);
        memset(Q, 0, MAXN);
        memset(P, 0, MAXN);
        memset(G, 0, MAXN*MAXN);
        cout << endl;
    }
    return 0;
}
/*
Задача 9а. [5.3.1] bfs.c
 Напишете програма за обхождане на граф в ширина (BFS(1))

Вход:
На входа се задава най-напред броя на дъгите на ориентиран граф, а после списък от тези дъги.
Списъкът се състои от не повече от 1000 дъги, зададени с двойки номера на върхове - начало, край.
Върховете на графа са номерирани с последователни цели положителни числа, започвайки от 1.
 .
 Изход:
 Отпечатва се списък (редица) от върховете на графа, получени при обхождането му в ширина. Първият член на редицата трябва да бъде 1.

 Пример:
3
 1 2
 2 3
 1 4

Решение на примера:
1 2 4 3
*/