UVa 762 - We Ship Cheap

/*
    RTE  |
            - got two RTE due to the recursion function (path()), so be careful of it.
    RTE  |

    WA

    Finally, Accepted

    Nice Problem for beginning.

    Algorithm: BFS
    with printing the Path

*/

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

#define sf scanf
#define pf printf
#define psb push_back
#define fast ios_base::sync_with_stdio(false)

typedef map<string, int>mpsi;
typedef map<int, string>mpis;
typedef long long LL;

const int high = 11115;
mpsi mp;
mpis rmp;

vector<LL>adj[high];
vector<LL>nodelist;
LL visited[high], par[high];
bool isPath = true;

void CLR()
{
    for(int i=0; i<high; i++)
    {
        adj[i].clear();
        visited[i] = 0;
        par[i] = 0;
    }

    mp.clear();
    rmp.clear();
    nodelist.clear();
    isPath = true;
}

void BFS(int s)
{
    visited[s] = 1;

    queue<LL>Q;

    Q.push(s);

    //par[s] = s;

    while(!Q.empty())
    {
        LL u = Q.front();
        Q.pop();

        LL sze = adj[u].size();

        for(LL i=0; i<sze; i++)
        {
            LL v = adj[u][i];

            if(!visited[v])
            {
                visited[v] = 1;
                Q.push(v);
                par[v] = u;
            }
        }
    }
}

void path(LL i, LL j)
{
    //cout << i << " " << j << "\n";

    if(i == j)
    {
       return;
    }

    else if(par[j] == 0)
    {
        isPath = false;
        return;
    }

    else
    {
        path(i , par[j]);
        nodelist.push_back(par[j]);
    }
}

int main()
{
    fast;
    LL i , edges, num = 0, tc=0;
    string x , y;

    while(cin >> edges)
    {
        CLR();

        num = 0;

        if(tc)
        {
            cout << "\n";
        }

        tc=1;

        for(i=0; i<edges; i++)
        {
            cin >> x >> y;

            if(mp[x] == 0)
            {
                num += 1;

                mp[x] = num;

                rmp[mp[x]] = x;
            }

            if(mp[y] == 0)
            {
                num += 1;
                mp[y] = num;
                rmp[mp[y]] = y;
            }

            //cout << mp[x] << " " << mp[y] << "\n";

            adj[mp[x]].psb(mp[y]);
            adj[mp[y]].psb(mp[x]);
        }

        cin >> x >> y;

        LL src = mp[x];
        LL des = mp[y];

        //cout << src << " " << des << "\n";

        if(src > 0 && des > 0)
        {
             BFS(src);

            path(src , des);
        }

        else
        {
            isPath = false;
        }

        nodelist.push_back(des);

        LL sze = nodelist.size();

        if(isPath)
        {
            for(i=0; i<sze-1; i++)
            {
                cout << rmp[nodelist[i]] << " " << rmp[nodelist[i+1]] << "\n";
            }
        }

        else
        {
            cout << "No route\n";
        }
    }

    return 0;
}