[UVa] 627 - The Net

Pretty simple and somewhat forced towards the solution.
Counting number of nodes and shortest path. You have to print the path too.
It's simply BFS. The pi[ ] array comes handy to print the path.

Method: BFS (Use the pi array)

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>

#define WHITE 0
#define GREY 1
#define BLACK 3
#define INF 0
#define NIL -1

using namespace std;

bool color[400], adj[400][400];
int d[400], p[400];
char in[100000];

bool bfs( int s, int des, int n ) {
 int u, v;
 for (u=0 ; u<=300 ; u++) {
  color[u] = WHITE;
  d[u] = INF;
  p[u] = NIL;
 }
 color[s] = GREY;
 d[s] = 0;
 p[s] = NIL;
 
 queue<int> q;
 q.push(s);
 while (!q.empty()) {
  u = q.front();
  q.pop();
  for (v=1 ; v<=n ; v++) {
   if (adj[u][v] && color[v]==WHITE) {
    color[v] = GREY;
    d[v] = d[u]+1;
    p[v] = u;
    q.push(v);
    if (v == des) {
     return true;
     
    }
   }
  }
  color[u] = BLACK;
 }
 return false;
}

void print_path(int v) {
 int i, j, pr[1000];
 for (i=v, j=0 ; i>0 ; i=p[i], j++) pr[j] = i;
 for (--j ; j>0 ; j--) printf("%d ",pr[j]);
 printf("%d\n",pr[j]);  //|Last one can't have
}    //|can't have blank space
    //|after it

int main( void ) {


 int i, j, c, n, u, v, nodes, conn;
 char *p;

 while ( scanf("%d",&nodes) == 1 ) {
  getchar(); // Back off for gets()
  
  for (i=0 ; i<=300 ; i++) { 
   for (j=0 ; j<=300 ; j++) adj[i][j] = false;
  }
  
  n = nodes;
  
  while (nodes--) {
   gets(in);
   p = strtok(in,"-,");
   sscanf(p,"%d",&i);
   p = strtok(NULL,"-,");
   while (p) {
    sscanf(p,"%d",&c);
    adj[i][c] = true; //|Connections are !bidirectional
    p = strtok(NULL,"-,");
   }
  }
  
  
  scanf("%d",&conn);
  
  printf("-----\n");
  
  for (i=1 ; i<=conn ; i++) {
   scanf("%d %d",&u, &v);
   if (bfs(u,v,n)) {
    print_path( v );
   } else {
    printf("connection impossible\n");
   }
  }
 }
}