UVA 10009 - All Roads Lead Where - Solution

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

class Graph{
    int V;
    list<int>*adj;
public:
    Graph(int V){this->V=V; adj=new list<int>[V]; }
    ~Graph() {delete []adj;}
    void addEdge(int u,int v){adj[u].pb(v); adj[v].pb(u); }
    void 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);
                    parent[*i]=s;
                    visited[*i]=true;
                    if (*i==dest)
                    {
                        print(parent,dest);
                        return;
                    }
                }
            }
        }
    }
    void print(int parent[],int dest)
    {
        vector<int>path;
        while (parent[dest]!=dest)
        {
            path.pb(dest);
            dest=parent[dest];
        }
        path.pb(dest);
        int l=path.size();
        for (int i=l-1;i>-1;--i)
            printf("%C",path[i]+'A');
        printf("\n");
    }
};

int main()
{
    int tc,n,q,s,d;
    string a,b;
    scanf("%d",&tc);
    while (tc--)
    {
        Graph g(30);
        scanf("%d%d",&n,&q);
        getchar();
        while (n--)
        {
            cin>>a>>b;
            s=a[0]-'A';
            d=b[0]-'A';
            g.addEdge(s,d);
        }
        while (q--)
        {
            cin>>a>>b;
            s=a[0]-'A';
            d=b[0]-'A';
            g.BFS(s,d);
        }
        if (tc) printf("\n");
    }
    return 0;
}