King Arthur's Knights
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1518 Accepted Submission(s): 645
Special Judge
Problem Description
I am the bone of my sword. Steel is my body, and the fire is my blood.
- from Fate / Stay Night
You must have known the legend of King Arthur and his knights of the round table. The round table has no head, implying that everyone has equal status. Some knights are close friends with each other, so they prefer to sit next to each other.
Given the relationship of these knights, the King Arthur request you to find an arrangement such that, for every knight, his two adjacent knights are both his close friends. And you should note that because the knights are very united, everyone has at least half of the group as his close friends. More specifically speaking, if there are N knights in total, every knight has at least (N + 1) / 2 other knights as his close friends.
Input
The first line of each test case contains two integers N (3 <= N <= 150) and M, indicating that there are N knights and M relationships in total. Then M lines followed, each of which contains two integers ai and bi (1 <= ai, bi <= n, ai != bi), indicating that knight ai and knight bi are close friends.
Output
For each test case, output one line containing N integers X1, X2, ..., XN separated by spaces, which indicating an round table arrangement. Please note that XN and X1 are also considered adjacent. The answer may be not unique, and any correct answer will be OK. If there is no solution exists, just output "no solution".
Sample Input
3 3
1 2
2 3
1 3
4 4
1 4
2 4
2 3
1 3
Sample Output
1 2 3
1 4 2 3
Source
2012 Multi-University Training Contest 4
Recommend
zhoujiaqi2010
題意：一個圓桌，安排座位。每個人的左右都要是自己的朋友。已知每個人都有一半以上的人是他的朋友。這個題應該用哈密頓回路做的，但是那個前提使得不
可能無解，所以帶回溯的深搜可以過，這樣就變成和經典素數環一樣的了。
感想：
1、首先建圖是無向圖啊，同學！！！開始就是這裡沒注意啊喂。要re[a][b]=true,re[b][a]=true;
2、你居然漏打！=EOF，不超時才怪。。。。難怪比完賽下來搜解題報告除了下標起始位置不同，幾乎一摸一樣你的過不了啊。。。。
代碼：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
bool re[155][155];
int ok[155];
bool vis[155];
int n,m;
int flag;
void dfs(int a,int pos)
{
if(flag==1)
return;
if(pos==n+1)
{
if(re[ok[1]][ok[n]])
{
for(int i=1;i<=n;i++)
printf("%d%c",ok[i],i==n?'\n':' ');
flag=1;
}
}
else
{
for(int i=2;i<=n;i++)
{
if(re[a][i]&&!vis[i])
{
vis[i]=true;
ok[pos]=i;
//printf("test: %d %d\n",pos,i);
dfs(i,pos+1);
//if(flag==1)
//break;
vis[i]=false;
}
}
}
}
int main()
{
int a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(vis,0,sizeof(vis));
memset(re,0,sizeof(re));
memset(ok,0,sizeof(ok));
flag=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
re[a][b]=true;
re[b][a]=true;
}
ok[1]=1;
dfs(1,2);
if(!flag)
printf("no solution\n");
}
return 0;
}
另一個回溯到主函數再輸出結果的代碼：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
bool re[155][155];
int ok[155];
bool vis[155];
int n,m;
int flag;
void dfs(int a,int pos)
{
if(flag==1)
return;
if(pos==n+1)
{
if(re[ok[1]][ok[n]])
flag=1;
//return;
}
else
{
for(int i=2;i<=n;i++)
{
if(re[a][i]&&!vis[i]&&flag==0)
{
vis[i]=true;
ok[pos]=i;
//printf("test: %d %d\n",pos,i);
dfs(i,pos+1);
//if(flag==1)
//break;
vis[i]=false;
}
}
}
}
int main()
{
int a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(vis,0,sizeof(vis));
memset(re,0,sizeof(re));
memset(ok,0,sizeof(ok));
flag=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
re[a][b]=true;
re[b][a]=true;
}
ok[1]=1;
dfs(1,2);
if(flag)
{
for(int i=1;i<=n;i++)
printf("%d%c",ok[i],i==n?'\n':' ');
}
else printf("no solution\n");
}
return 0;
}
