题解 | 插队

//普通遍历会爆时间复杂度
// #include <iostream>
// using namespace std;
// #include<list>
// #include<algorithm>

// void printL(string s){
//        cout<<s<<" ";
// }

// int main() {
//    int n,m;
//    cin>>n>>m;
//    list<string>L;
//    for(int i=0;i<n;i++){
//     string s;
//     cin>>s;
//     L.push_back(s);
//    }
//    while(m--){
//        string s1,s2;
//        cin>>s1>>s2;
//        auto pos_s1=find(L.begin(),L.end(),s1);
//        L.erase(pos_s1);
//        auto pos_s2=find(L.begin(),L.end(),s2);
//        L.insert(pos_s2,s1);
//    }
//    for_each(L.begin(),L.end(), printL);
// }
// 64 位输出请用 printf("%lld")

//需要用map存储每个成员的迭代器
#include <iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<map>
void printL(string s){
       cout<<s<<" ";
}

int main() {
   int n,m;
   cin>>n>>m;
   list<string>L;
   map<string,list<string>::iterator>m1;
   for(int i=0;i<n;i++){
    string s;
    cin>>s;
    L.push_back(s);
    list<string>::iterator nowinsetpos=--L.end();
    m1.insert(make_pair(s,nowinsetpos));
   }
   while(m--){
       string s1,s2;
       cin>>s1>>s2;
       auto pos_s1=m1[s1];;
       L.erase(pos_s1);
       auto pos_s2=m1[s2];
       L.insert(pos_s2,s1);
   }
   for_each(L.begin(),L.end(), printL);
}