UVA 627 - The Net -Solution

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
class Graph{
    int V;
    list<int>*adj;
public:
    Graph(int V);
    ~Graph();
    void addEdge(int u, int v);
    void BFS(int s,int dest);
};
Graph::Graph(int V) //construtor
{
    this->V=V;
    adj=new list<int >[V];
}
Graph::~Graph() //destructor
{
    delete []adj;
}
void Graph::addEdge(int u,int v)
{
    adj[u].pb(v);
}
void Graph::BFS(int s,int dest)
{
    bool visited[V];
    int parent[V];
    memset(visited,false,sizeof(visited));
    list<int>q;
    list<int>::iterator i;
    q.pb(s);
    visited[s]=true;
    parent[s]=s;
    while (!q.empty())
    {
        s=q.front();
        q.pop_front();
        for (i=adj[s].begin();i!=adj[s].end();++i)
        {
            if (!visited[*i])
            {
                q.pb(*i);
                visited[*i]=true;
                parent[*i]=s;
                if (*i==dest)
                {
                    vector<int>path;
                    int t=*i;
                    while (parent[t]!=t)
                    {
                        path.pb(t);
                        t=parent[t];
                    }
                    path.pb(t);
                    t=path.size();
                    for (int j=t-1;j>-1;j--)
                    {
                        printf("%d",path[j]);
                        if (j) printf(" ");
                        else printf("\n");
                    }
                    return;
                }
            }
        }
    }
    printf("connection impossible\n");
    return;
}

int main()
{
    int routers;
    while (scanf("%d",&routers)!=EOF)
    {
        Graph g(routers+1);
        char s[1000];
        getchar();
        while (routers--)
        {
            gets(s);
            char *pch;
            pch=strtok(s,"-,");
            int id=atoi(pch);
            pch=strtok(NULL,"-,");
            while (pch!=NULL)
            {
                int sees=atoi(pch);
                g.addEdge(id,sees);
                pch=strtok(NULL,"-,");
            }
        }
        int m;
        scanf("%d",&m);
        printf("-----\n");
        while (m--)
        {
            int s,dest;
            scanf("%d%d",&s,&dest);
            g.BFS(s,dest);
        }
    }
    return 0;
}