627Uvaoj.cpp

#include<bits/stdc++.h>
using namespace std;

vector<int>adj[100000];
int visited[100000];
int level[100000];
int p[100000];
int flag=1;
int path[100000];
int bfs(int s, int e, int n)
{
    queue<int>Q;
    Q.push(s);
    visited[s]=1;
    p[s]=s;

    while(!Q.empty())
    {
        if(visited[e]==1)
            break;
        int u=Q.front();
        Q.pop();
        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i];
            if(visited[v]==0)
            {
                visited[v]=1;
                Q.push(v);
                p[v]=u;
            }
        }
    }

    if(p[e]==0)
    {
        cout<<"connection impossible"<<endl;
        flag=0;
        return 0;
    }
    else
    {

        int now=e;
        int i=0;
        path[i++]=e;
        while(now!=s)
        {
            now=p[now];
            path[i++]=now;
        }
        reverse(path, path+i);
        return i;
    }
    return 0;


}
int main()
{
    int n;
    char garbage;
    while((cin>>n) and n)
    {
        int m=n;
        cout<<"-----"<<endl;
        for(int i=0; i<m+5; i++)
            adj[i].clear();
        while(n--)
        {
            string line;
            int connected;
            int node;
            cin>>node;
            getline(cin,line);
            stringstream ss(line);
            while(ss>>garbage>>connected)
            {
                adj[node].push_back(connected);
            }
        }

        fill(visited, visited+m+5,0);
        fill(level, level+m+5,0);
        fill(p, p+m+5,0);
        int t;
        cin>>t;
        while(t--)
        {
            int a, b;
            cin>>a>>b;
            int i=bfs(a, b, m);

            if(flag)
            {
                int path_size;
                path_size=sizeof(path)/sizeof(int);
                for(int j=0; j<i; j++)
                {
                    cout<<path[j];
                    if(j!=i-1)
                        cout<<" ";
                }
                cout<<endl;
            }
            flag=1;
            fill(visited, visited+m+5,0);
            fill(level, level+m+5,0);
            fill(p, p+m+5,0);

        }

    }
}