C++14(g++5.4) 解法, 执行用时: 202ms, 内存消耗: 15584K, 提交时间: 2020-10-13 18:43:06

#include"bits/stdc++.h"
using namespace std;
list<int> a[100001],b[100001];

int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++)
		{
			a[i].clear();
			a[i].push_back(i);
			b[i].clear(); 
			b[i].push_back(i);
		}
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			a[x].splice(a[x].end(),a[y]);
			b[y].splice(b[y].end(),b[x]);
			swap(a[x],b[y]);
			swap(b[y],b[x]);
			
			a[y].clear();
			b[y].clear();
			
		}
		cout<<a[1].size()<<" ";
		for(list<int>::iterator it=a[1].begin();it!=a[1].end();it++)
		{
			cout<<*it<<" ";
	 	} 
	 	cout<<endl;
	 	
	}

	return 0;
 } 

C++(g++ 7.5.0) 解法, 执行用时: 198ms, 内存消耗: 12524K, 提交时间: 2022-09-19 11:23:54

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
const int N=1e5+10;
list<int> l1[N],l2[N];//l1存逆序  l2存顺序 
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++)
		{
			l1[i].clear();
			l2[i].clear();
			l1[i].push_back(i);
			l2[i].push_back(i);
		}
		for(int i=1;i<=m;i++)
		{
			int a,b;
			cin>>a>>b;
			l1[a].splice(l1[a].end(),l1[b]);
			l2[b].splice(l2[b].end(),l2[a]);
			swap(l1[a],l2[b]);
			swap(l2[b],l2[a]);
		}
		printf("%d ",l1[1].size());
		for(auto s:l1[1])
			printf("%d ",s);
		printf("\n");
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 210ms, 内存消耗: 15756K, 提交时间: 2019-10-22 18:12:26

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

list<int>X[100005],Y[100005];
int main()
{
	int i,a,b,n,m;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=1;i<=n;i++)X[i].clear(),X[i].push_back(i),Y[i].clear(),Y[i].push_back(i);
		while(m--) 
		{
			scanf("%d%d",&a,&b);
			X[a].splice(X[a].end(),X[b]),Y[b].splice(Y[b].end(),Y[a]);
			swap(X[a],Y[b]),swap(Y[a],Y[b]);
			X[b].clear(),Y[b].clear();
		}
		printf("%d",X[1].size());
		for(list<int>::iterator j=X[1].begin();j!=X[1].end();j++)printf(" %d",*j);
		printf("\n");
	}
	return 0;
}