HomeWork1

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 #include <memory.h>
  5 
  6 using namespace std;
  7 
  8 int far[100010],represent[100010],true_num,int_far,int_son,int_name1,int_name2,state[100010];
  9 map <string, int> name_str_int;
 10 string name_int_str[100010];
 11 vector<int> son[100010],left_next[100010];
 12 int input[100010];
 13 
 14 int GetNum(string);
 15 int dfs(int);
 16 int Represent(int);
 17 
 18 int main()
 19 {
 20     cin.sync_with_stdio(0);
 21     cin.tie(0);
 22 
 23     int N,M;
 24     string Father_i,Son_i,Name1_i,Name2_i;
 25 
 26     name_str_int.clear();
 27     true_num=0;
 28     memset(state,0,sizeof(state));
 29     for(int i=1; i<100010; i++)
 30         represent[i]=i;
 31 
 32     cin>>N;
 33     while(N--)
 34     {
 35         cin>>Father_i>>Son_i;
 36         int_far=GetNum(Father_i);
 37         int_son=GetNum(Son_i);
 38         son[int_far].push_back(int_son);
 39         far[int_son]=int_far;
 40     }
 41 
 42     cin>>M;
 43     for(int i=1; i<=M; i++)
 44     {
 45         cin>>Name1_i>>Name2_i;
 46         int_name1=name_str_int.at(Name1_i);
 47         int_name2=name_str_int.at(Name2_i);
 48         if(int_name1==int_name2)
 49             input[i]=int_name1;
 50         else
 51         {
 52             left_next[int_name1].push_back(int_name2);
 53             left_next[int_name1].push_back(i);
 54         }
 55     }
 56     dfs(1);
 57     for(int i=1; i<=M; i++)
 58         cout<<name_int_str[input[i]]<<endl;
 59 
 60 }
 61 
 62 int Represent(int number)
 63 {
 64     while(number!=represent[number])
 65         number=represent[number];
 66     return number;
 67 }
 68 
 69 int dfs(int cur_node)
 70 {
 71     //cout<<"-->"<<name_int_str[cur_node];
 72     state[cur_node]=1;
 73 
 74     for(int i=0; i<left_next[cur_node].size(); i=i+2)
 75     {
 76         if(state[left_next[cur_node][i]])
 77         {
 78             input[left_next[cur_node][i+1]]=Represent(left_next[cur_node][i]);
 79         }
 80         else
 81         {
 82             left_next[left_next[cur_node][i]].push_back(cur_node);
 83             left_next[left_next[cur_node][i]].push_back(left_next[cur_node][i+1]);
 84         }
 85     }
 86 
 87     for(int i=0; i<son[cur_node].size(); i++)
 88         dfs(son[cur_node][i]);
 89 
 90     represent[cur_node]=far[cur_node];
 91     //state[cur_node]=2;
 92 }
 93 
 94 int GetNum(string name)
 95 {
 96     if(!name_str_int.count(name))
 97     {
 98         name_int_str[++true_num]=name;
 99         name_str_int.insert(pair<string, int> (name, true_num));
100         return true_num;
101     }
102     return name_str_int.at(name);
103 }