题解 | 插队

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;

map<string,int> name_to_id;
vector<string> id_to_name(N);
int n,m;
int pre[N],net[N];


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	
	string str;
	for(int i=1;i<=n;i++){
		cin>>str;
		name_to_id[str]=i;
		id_to_name[i]=str;
	}
	
	net[0]=1;
	pre[n+1]=n;
	for(int i=1;i<=n;i++){
		pre[i]=i-1;
		net[i]=i+1;
	}
	
	string x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		int u_id=name_to_id[x];
		int v_id=name_to_id[y];
		//将x顾客从链表中拿出 
		int u_pre_id=pre[u_id];
		int u_net_id=net[u_id];
		net[u_pre_id]=u_net_id;
		pre[u_net_id]=u_pre_id;
		//将x顾客插入到y顾客的前面 
		int v_pre_id=pre[v_id];
		net[v_pre_id]=u_id;
		pre[u_id]=v_pre_id;
		net[u_id]=v_id;
		pre[v_id]=u_id;
	}
	for(int i=net[0];i!=n+1;i=net[i]){
		cout<<id_to_name[i]<<" ";
	}
    return 0;
}