UVA 762 - We Ship Cheap -Solution

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
map<string,int>msi;
map<int,string>mis;
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;
                    }
                }
            }
        }
        printf("No route\n");
    }
    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>0;--i)
            cout<<mis[path[i]]<<" "<<mis[path[i-1]]<<endl;
    }
};

int main()
{
    int n,f=0;
    string a,b;
    while (scanf("%d",&n)!=EOF)
    {
        Graph g(2000);
        getchar();
        int ind=-1;
        while (n--)
        {
            cin>>a>>b;
            if (msi.find(a)==msi.end())
            {
                msi[a]=++ind;
                mis[ind]=a;
            }
            if (msi.find(b)==msi.end())
            {
                msi[b]=++ind;
                mis[ind]=b;
            }
            g.addEdge(msi[a],msi[b]);
        }
        cin>>a>>b;
        if (f) cout<<endl;
        if (msi.find(a)==msi.end() || msi.find(b)==msi.end()) printf("No route\n");
        else g.BFS(msi[a],msi[b]);
        f=1;
        msi.clear();
        mis.clear();
    }
    return 0;
}