题解 | 插队

import sys
input = sys.stdin.readline
n,m =map(int,input().split())
name_list = input().split()
#用于存储名字到id的一个字典
name_to_id = {}
#用于最后输出顺序的id_to_name
id_to_name = [""]*(n+1)


#数组模拟双向链表
#存前驱pre_arr[i]存的是id为i的前驱
pre_arr = [0]*(n+2)
#存后继next_arr[i]存的是id为i的后继
next_arr = [0]*(n+2)

#初始化，分配id 1-n
for i,name in enumerate(name_list):
    #实际上就是其原始位置下标，作为id
    user_id = i+1
    name_to_id[name]=user_id
    #按顺序记名字
    id_to_name[user_id]=name

#初始化前驱后继
next_arr[0]=1#头结点位置为0，其后继为1
pre_arr[n+1]=n#尾节点n+1,前驱为n
for i in range(1,n+1):
    pre_arr[i]=i-1
    next_arr[i]=i+1

for i in range(m):
    #待插入名字，与被插入名字
    insert_name,origin_name = input().split()
    #获取其相应的下标
    insert_id = name_to_id[insert_name]
    origin_id = name_to_id[origin_name]

    #1.将insert_name从双向链表中取下
    #先获取，insert_id的前驱和后继
    pre_insert_id =  pre_arr[insert_id]
    next_insert_id = next_arr[insert_id]

    #再修改双链表,原来insert_id的前驱直接指向insert_id的后继
    pre_arr[next_insert_id]=pre_insert_id
    next_arr[pre_insert_id]=next_insert_id

    #2.将insert_id插入origin_id前
    #先获取origin_id的前驱
    pre_origin_id=pre_arr[origin_id]
    
    #将insert_id插入其中
    #insert_id的前驱变为origin_id的前驱
    pre_arr[insert_id]=pre_origin_id
    #origin_id的前驱的后继变为insert_id
    next_arr[pre_origin_id]=insert_id   
    #origin_id的前驱变为insert_id
    pre_arr[origin_id]=insert_id
    #insert_id的后继变为origin_id
    next_arr[insert_id]=origin_id

    #输出结果：
    result=[]
    #cur为工作指针
cur_id = next_arr[0]
while cur_id != n+1:
    result.append(id_to_name[cur_id])
    #cur_id指向下一个节点
    cur_id = next_arr[cur_id]
print(" ".join(result))