题解 | 插队

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define endl '\n'
#define INF 2e18
#define ull unsigned long long
#define pq priority_queue<int>
int mod = 1000000007;
const int N = 2e6 + 5;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int days[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

//快速幂
inline int ksm(int a, int b)
{
	int mod = 1000000007;
	int ans = 1;
	a %= mod;
	while (b)
	{
		if (b & 1)ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans % mod;
}

int flag;
map<string, int>Id;
map<int, string>name;

struct node
{
	int id;
	node* next;
	node* front;
};

map<string, node*>mp;

void solve()
{
	int n, m; cin >> n >> m;

	node* head = new node;
	head->front = NULL;
	head->next = NULL;
	head->id = 0;

	node* tail = new node;
	tail->id = n + 1;
	tail->next = NULL;
	tail->front = head;
	head->next = tail;

	for (int i = 1; i <= n; i++)
	{
		string s; cin >> s;
		Id[s] = ++flag;
		name[flag] = s;
		node* New = new node;
		New->id = flag;
		node* t = tail->front;
		t->next = New;
		New->front = t;
		New->next = tail;
		tail->front = New;
		mp[s] = New;
	}
	while (m--)
	{
		string x, y; cin >> x >> y;
		int a = Id[x], b = Id[y];
		node* aa = mp[x];
		node* bb = mp[y];
		aa->front->next = aa->next;
		aa->next->front = aa->front;
		aa->next = bb;
		aa->front = bb->front;
		bb->front->next = aa;
		bb->front = aa;
	}

	node* t = head;
	t = t->next;
	while (t != tail)
	{
		cout << name[t->id] << ' ';
		t = t->next;
	}
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}