题解 | 插队

#include <iostream>
#include <list>
#include <pthread.h>
#include <string>
#include <algorithm>
#include <iterator>
#include <unordered_map>
// 迭代器辅助函数 记得包含上面那个iterator头文件
// advance(it, 3);         // 前进3个位置
// int dist = distance(v.begin(), it); // 计算距离
// auto prev_it = prev(it, 2);         // 前一个迭代器
// auto next_it = next(it, 2);         // 后一个迭代器
using namespace std;
//用下面这个方法只过了三个数据 狠狠超时 应该是这个find效率太低了 remove也是 这两个都是O(n)的复杂度
/*int main() {
    int n,m;
    cin>>n>>m;
    list<string>lis;
    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;
        lis.push_back(str);
    }
    for(int i=0;i<m;i++)
    {
        string s1;
        string s2;
        cin>>s1>>s2;
        // remove的操作也会改变迭代器的指向 所以应该优先进行
        lis.remove(s2);
        auto it=find(lis.begin(),lis.end(),s1);
        //注意insert是在对应的it前面插入 不是在后面
        //还有这个it表示的是一个位置 并不会一直追踪这个元素 如果元素位置变动了 这个it还是会指向原来的位置 一定要注意好这一点
        it++;
        lis.insert(it,s2);
    }
    for(auto it=lis.begin();it!=lis.end();it++)
    {
        cout<<*it<<" ";
    }
}
// 64 位输出请用 printf("%lld")
*/
//  下面使用哈希表来保存字符串的迭代器 这样就把删除和查找复杂度降低到了O(1)
// 对于链表来说 插入不会使得迭代器失效 但是删除会使得被删除的元素的迭代器失效 所以需要更新这个迭代器 insert的返回值就是新的迭代器
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    list<string>lis;
    unordered_map< string, list<string>::iterator >mp;
    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;
        lis.push_back(str);
        mp[str]=prev(lis.end());
    }
    for(int i=0;i<m;i++)
    {
        string s1;
        string s2;
        cin>>s1>>s2;
        auto it1=mp[s1];
        auto it2=mp[s2];
        lis.erase(it1);
        auto new_it1=lis.insert(it2,s1);
        mp[s1]=new_it1;
    }
    for(auto it:lis)
    {
        cout<<it<<" ";
    }
}

使用哈希表优化了链表元素的查找和删除 并且处理了删除元素的时候迭代器失效的情况 从而满足题目要求