ACM UVA (10009)

/*
 *******************************************************************************
 *
 * Filename: 10009.cpp
 *
 * Description:
 *
 * Version: 0.1
 * Created: 4/17/2009 8:06:13 AM
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

#include <iostream>
#include <string>

using namespace std;

#define CITY_NAME_LEN 20

// A-Z city

int city_array[26];

string find_path(char city1, char city2);
string find_road_to_rome(char city);

int main(int argc, char **argv)
{
    int case_num = 0;
    int road_num = 0;
    int query_num = 0;

    memset(city_array, 0, 26 * sizeof(int));
    cin >> case_num;
    while (case_num != 0) {
        cin >> road_num >> query_num;
        while (road_num != 0) {
            string city_name1;
            string city_name2;
            cin >> city_name1 >> city_name2;
            city_array[city_name2[0]-'A'] = city_name1[0] - 'A';
            
            road_num--;
        }
        while (query_num != 0) {
            string city_name1;
            string city_name2;
            cin >> city_name1 >> city_name2;
            cout << find_path(city_name1[0], city_name2[0]) << endl;
            query_num--;
        }

        case_num--;

        //
        // There should not be any blank line
        // after the last case
        //
        if (case_num != 0) {
            cout << endl;
        }
    }
}


string find_path(char city1, char city2)
{
    string road2rome1 = find_road_to_rome(city1);
    string road2rome2 = find_road_to_rome(city2);

    int i = road2rome1.size()-1;
    int j = road2rome2.size()-1;

    while ( (i != -1) && (j != -1) && (road2rome1[i] == road2rome2[j])) {
        i--;
        j--;
    }

    string path;
    for (int k = 0; k <= i+1; k++) {
        path.push_back(road2rome1[k]);
    }
    for (int k = j; k >= 0; k--) {
        path.push_back(road2rome2[k]);
    }

    return path;
}

string find_road_to_rome(char city)
{
    string road2rome;

    while (city != 'R') {
        road2rome.push_back(city);
        city = city_array[city-'A'] + 'A';
    }
    road2rome.push_back('R');

    return road2rome;
}