762 - We Ship Cheap

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cstring>
#define M 700
using namespace std;

bool list[M][M];
char Node[M][10];
int path[M],N;

int FindID(char[]);
void PrintPath(int,int);
bool BFS(int,int);

int main()
{
    bool status,f=true;
    int i,n,xid,yid;
    char X[3],Y[3];
    //freopen("in.txt","r",stdin);

    while(scanf("%d\n",&n)==1)
    {
        N=0;
        memset(list,false,sizeof(list));
        memset(Node,'\0',sizeof(Node));

        for(i=0;i<n;i++)
        {
            scanf("%s%s",X,Y);
            xid=FindID(X);
            yid=FindID(Y);

            if(xid<0)
            {
                xid=N;
                Node[N][0]=X[0];
                Node[N][1]=X[1];
                Node[N][2]='\0';
                N++;
            }

            if(yid<0)
            {
                yid=N;
                Node[N][0]=Y[0];
                Node[N][1]=Y[1];
                Node[N][2]='\0';
                N++;
            }

            list[xid][yid]=list[yid][xid]=true;
        }

        scanf("%s%s",X,Y);
        xid=FindID(X);
        yid=FindID(Y);

        if(xid==-1 || yid==-1)
        {
            if(f)
                f=false;
            else
                printf("\n");
            if(strcmp(X,Y))
                printf("No route\n");
            else
                printf("%s %s\n",X,Y);
            continue;
        }


        status = BFS(xid,yid);
        if(xid==yid)status=true;

        if(f)
            f=false;
        else
            printf("\n");

        if(!status)
            printf("No route\n");
        else
            PrintPath(xid,yid);
    }
    exit(0);
}

int FindID(char node[])
{
    int i;
    for(i=0;i<N;i++)
        if(Node[i][0]==node[0]&&Node[i][1]==node[1])
            return i;
    return -1;
}

bool BFS(int x,int y)
{
    int i,h;
    int color[M];
    queue<int>Q;
    memset(color,0,sizeof(color));

    color[x]=1;Q.push(x);
    while(!Q.empty())
    {
        h=Q.front();Q.pop();

        for(i=0;i<N;i++)
        {
            if(list[h][i]&&color[i]==0)
            {
                path[i]=h;
                color[i]=1;
                if(i==y)return true;
                Q.push(i);
            }
        }
    }
    return false;
}

void PrintPath(int x,int y)
{
    int s,d;

    d=y,s=path[y];

    if(s==x)
    {
        printf("%s %s\n",Node[s],Node[d]);
        return;
    }
    PrintPath(x,s);
    printf("%s %s\n",Node[s],Node[d]);
}