UVA 10009 - All Roads Lead Where?(cpp file)

Problem Type : GRAPH(BFS)


#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<vector>
#define MAX 10000
using namespace std;
map<string,char>mymap;
map<char,int>color;
map<char,char>par;
vector<char>vcc[MAX],v;

void bfs(char start)
{
    int i;
    char u;
    queue<char>Q;
    Q.push(start);
    color[start]=1;
    par[start]=start;
    while(!Q.empty())
    {
        u=Q.front();

        Q.pop();
        int len=vcc[u].size();
        for(i=0; i<len; i++)
        {
            if(color[vcc[u][i]]!=1)
            {
                //printf("%c\n",vcc[u][i]);
                color[vcc[u][i]]=1;
                Q.push(vcc[u][i]);
                par[vcc[u][i]]=u;
            }
        }
    }
    return;
}
int main()
{
    int test,i,j,k,cas=0, n,m;
    string node1,node2;
    char c;
    scanf("%d",&test);

    while(test--)
    {
        if(cas!=0)
            printf("\n");
        cas++;
        scanf("%d %d",&n,&m);
        getchar();
        for(i=0;i<9999;i++)
        {
            vcc[i].clear();
        }
        while(n--)
        {

            cin >> node1 >> node2;
            if(mymap.find(node1)==mymap.end())
            {
                c=node1[0];
                mymap[node1]=c;
            }
            if(mymap.find(node2)==mymap.end())
            {
                c=node2[0];
                mymap[node2]=c;
            }
            char kp=mymap[node1];
            char pk=mymap[node2];
            vcc[kp].push_back(pk);
            vcc[pk].push_back(kp);

        }
        while(m--)
        {
            cin >> node1 >> node2;
            char start = mymap[node1];
            char des = mymap[node2];
            par.clear();
            color.clear();
            bfs(start);
            v.push_back(des);
            for(i=0; ; i++)
            {
                v.push_back(par[des]);
                //printf("%c",par[des]);
                if(par[des]==start)
                    break;
                des=par[des];
            }
          for(i=v.size()-1; i>=0; i--)
            {
                printf("%c",v[i]);
            }
            printf("\n");
            v.clear();
        }

    }

    return 0;
}