💡题解思路

✅ 本质模型：

本题可以视作图染色问题 + 圆排列约束，或者进一步建模为约束满足问题（CSP）。

✅ 解法一（枚举排列）：

对 $2n$ 个孩子进行全排列；

对于每个排列，判断是否所有敌对关系对的孩子都不相邻（即排列中相邻的编号对不能为敌人）；

找到第一个合法解则输出；

若没有，输出 No solution!。

该方法在 $n \leq 4$ 时效率尚可（$2n \leq 8$），但随着 $n$ 增大将不适用。

✅ 解法二（回溯 + 剪枝）：

用邻接矩阵 $enemy[i][j]$ 记录敌人关系；

从第一个位置开始递归放置孩子：

每次尝试放一个未放置的孩子；

若与前一个位置的孩子是敌人则跳过；

特殊注意：因为是圆桌，所以第一个和最后一个孩子也要检查是否为敌人；

一旦放置满 $2n$ 个孩子即输出解。

✅ 解法三（SAT or CSP求解器）：

构造约束转化为 2-SAT 或 CSP 问题，再用求解器处理，但比赛中较为复杂，不做展开。

🧠复杂度分析

最坏情况下是 $O((2n)!)$ 枚举所有可能排列，但实际可通过剪枝大大减少搜索空间；

本题目规模较小，$n \leq 200$，但敌对关系上限有限制，因此剪枝有效。

代码实现

#include<stdio.h>
#include<string.h>
#define M 407
using namespace std;
int ans[M],g[M][M];
bool map[M][M],vis[M];
int n,m;

void init()
{
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			if(i==j)
				g[i][j]=0;
	else
		g[i][j]=1;
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
}

void revese(int ans[M],int s,int t)//将ans数组中s到t的部分倒置
{
	int temp;
	while(s<t)
	{
		temp=ans[s];
		ans[s]=ans[t];
		ans[t]=temp;
		s++;
		t--;
	}
}

void Hamilton()
{
	int s=1,t;//初始化s取1号点
	int ansi=2;
	int i,j,w,temp;
	for(i=1;i<=n;i++)
		if(g[s][i])break;
	t=i;//取任意连接s的点为t
	vis[s]=vis[i]=true;
	ans[0]=s;
	ans[1]=t;
	while(true)
	{
		while(true)//从t向外扩展
		{
			for(i=1;i<=n;i++)
				if(g[t][i]&&!vis[i])
				{
					ans[ansi++]=i;
					vis[i]=true;
					t=i;
					break;
				}
			if(i>n)break;
		}
		//将当前得到的序列倒置，s和t互换，从t继续扩展，相当于在原来的序列上从s扩展
		w=ansi-1;
		i=0;
		revese(ans,i,w);
		temp=s;
		s=t;
		t=temp;
		//从新的t向外扩展，相当于在原来的序列上从s向外扩展
		while(true)
		{
			for(i=1;i<=n;i++)
				if(g[t][i]&&!vis[i])
				{
					ans[ansi++]=i;
					vis[i]=true;
					t=i;
					break;
				}
			if(i>n)break;
		}
		//如果s和t不相邻，进行调整
		if(!g[s][t])
		{
			for(i=1;i<ansi-2;i++)
				if(g[ans[i]][t]&&g[s][ans[i+1]])//取序列中一点i，使得ans[i]与t相连接且ans[i+1]与s相连
					break;
			//将从ans[i+1]到t部分的ans[]倒置
			w=ansi-1;
			i++;
			t=ans[i];
			revese(ans,i,w);
		}
		//如果当前s和t相连
		if(ansi==n)return;//如果当前序列中包含n个元素，算法结束
		//当前序列中的元素个数小于n，寻找点ans[i]，使得ans[i]与ans[]外一点相连
		for(j=1;j<=n;j++)
		{
			if(vis[j])continue;
			for(i=1;i<ansi-2;i++)
				if(g[ans[i]][j])
					break;
			if(g[ans[i]][j])
				break;
		}
		s=ans[i-1];
		t=j;
		revese(ans,0,i-1);//将ans[]中s到ans[i-1]部分的ans[]倒置
		revese(ans,i,ansi-1);//将ans[]中ans[i]到t的部分倒置
		ans[ansi++]=j;//将点j加入到ans[]的尾部
		vis[j]=true;
	}
}

int main()
{
	while(scanf("%d%d",&n,&m),n|m)
	{
		n*=2;
		init();
		int a,b;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			g[a][b]=g[b][a]=0;//巧妙的建立反图
		}
		Hamilton();
		printf("%d",ans[0]);
		for(int i=1;i<n;i++)
			printf(" %d",ans[i]);
		printf("\n");
	}
	return 0;
}