UVa - 10009 - All Roads Lead Where

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

vector <int> City[L];
int Vis[L], Path[L];
map <string, int> M;
map <int, char> M1;

void print_path(int v, int u){
    int p = Path[v];
    if(p != u)print_path(p, u);
    cout << M1[p];
}

void BFS(int src, int dest){
    queue <int> Q;
    Vis[src] = 1;
    Q.push(src);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        int sz = City[u].size();
        for(int i = 0; i < sz; i++){
            int v = City[u][i];
            if(!Vis[v]){
                Vis[v] = 1;
                Q.push(v);
                Path[v] = u;
            }
        }
    }
    print_path(dest, src);
    cout << M1[dest] << endl;
}

int main(){
    int test, n, q, f = 0;
    string start, endd;
    cin >> test;
    while(test--){
        cin >> n >> q;
        int k = 1;
        for(int i = 1; i <= n; i++){
            cin >> start >> endd;
            if(!M[start])M[start] = k, M1[k] = start[0], k++;
            if(!M[endd])M[endd] = k, M1[k] = endd[0], k++;
            City[M[start]].push_back(M[endd]);
            City[M[endd]].push_back(M[start]);
        }
        if(f)puts(""); f = 1;
        for(int i = 1; i <= q; i++){
            cin >> start >> endd;
            memset(Path, -1, sizeof(Path));
            memset(Vis, 0, sizeof(Vis));
            BFS(M[start], M[endd]);
        }
        M.clear(), M1.clear();
        for(int i = 1; i < k; i++)City[i].clear();
    }
    return 0;
}