Hihocoder - 15주 LCA

#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <vector>

using namespace std;

map<string, string> represent;
map<pair<string, string>, string> ans;
pair<string, string> a[100005];

string find_represent(string x){
    if (x == represent[x])
        return x;
    else{
        represent[x] = find_represent(represent[x]);
        return represent[x];
    }
}

void unionset(string x, string y){
    represent[find_represent(x)] = find_represent(y);
}

template <class T>
class Node{
/*
 *  This is a Tree Node class.
*/
    public:
        T field, parent;
        vector<T> son;
		vector<T> query;
		string color;

        Node(T myfield){
            field = myfield;
            son.clear();
			query.clear();
            parent = "";
			color = "white";
        }

		void add_query(T query_name){
			query.push_back(query_name);
		}

        void add_child(T child){
            son.push_back(child);
        }

        void set_parent(T sparent){
            parent = sparent;
        }
};

template <class T>
class GenTree{
    public:
        Node<T> *root;
        map<T, Node<T>* > nodes;

		GenTree(){}

        GenTree(T root_field){
            root = new Node<T>(root_field);
            root->parent = root_field;
            nodes.insert(pair<T, Node<T>* >(root_field, root));
        }

        Node<T>* add_node(T field, T parent = ""){
            Node<T> *node = new Node<T>(field);

            nodes[field] = node;
            if (parent!= ""){
                nodes[parent]->add_child(field);
                node->parent = parent;
            }
			else
				node->parent = field;

            return node;
        }

		void add_query(T field, T query_name){
			nodes[field]->add_query(query_name);
			nodes[query_name]->add_query(field);
		}

        void traverse(T field){
            stack<T> mystack;
            T temp_field;

			mystack.push(field);
            while (!mystack.empty()){
                temp_field = mystack.top();
                mystack.pop();
                cout<<temp_field<<endl;
				if (nodes[temp_field]->son.size() != 0){
					int size = 	nodes[temp_field]->son.size();
					for (int i=size-1; i>=0; i--)
						mystack.push(nodes[temp_field]->son[i]);
				}
				cout<<temp_field<<endl;
            }
        }

		void dfs(T field){
			int n = nodes[field]->son.size();
			int size = nodes[field]->query.size();
			string query_name, color, temp_name1, temp_name2;

			nodes[field]->color = "grey";
			if (size != 0){
				for (int i=0; i<size; i++){
					temp_name1 = nodes[field]->query[i];
					color = nodes[temp_name1]->color;
					if (color == "grey"){
						ans[pair<string, string>(field, temp_name1)] = temp_name1;
						ans[pair<string, string>(temp_name1, field)] = temp_name1;
					}
					else if (color == "black"){
						temp_name2 = find_represent(temp_name1);
						ans[pair<string, string>(field, temp_name1)] = temp_name2;
						ans[pair<string, string>(temp_name1, field)] = temp_name2;
					}
				}	
			}

			if (n != 0){
				for (int i=0; i<n; i++)		
				{
					T cur_son = nodes[field]->son[i];
					dfs(cur_son);
				}		
				//cout<<field<<" "<<nodes[field]->color<<endl;
				nodes[field]->color = "black";
				unionset(field, nodes[field]->parent);
			}
			else{
				//cout<<field<<" "<<nodes[field]->color<<endl;
				nodes[field]->color = "black";
				unionset(field, nodes[field]->parent);
			}
		}

};

int main()
{
    GenTree<string> mytree;
	int n, m;
	string name1, name2, root;

	cin>>n;
	for (int i=0; i<n; i++){
		cin>>name1>>name2;
		
		represent[name1] = name1;
		represent[name2] = name2; 
		if (i==0){
			root = name1;
			mytree.add_node(name1);
			mytree.add_node(name2, name1);
		}
		else
			mytree.add_node(name2, name1);
	}
	cin>>m;
	for (int i=0; i<m; i++){
		cin>>name1>>name2;
		mytree.add_query(name1, name2);
		a[i] = pair<string, string>(name1, name2);
	}

	mytree.dfs(root);

	for (int i=0; i<m; i++){
		cout<<ans[a[i]]<<endl;
	}
	
    return 0;
}