NC15195. 腰带图
描述
一个n个点m条边的无向图，它若满足以下性质，我们就称它为腰带图：
(1)点pi和点p(i+1) mod (n/2)间有边相邻。
(2)点pi+n/2和点pn/2+(i+1) mod (n/2)间有边相邻。
(3)点pi和点pi+n/2间有边相邻。
注：x mod y为x除以y的余数。
现在给你一个无向图，请判断他是否是腰带图。
输入描述
输入的第一行有一个正整数T，代表询问数。
每个询问各占1+m行，当中的第1行有两个正整数n,m分别代表点数和边数，接下来m行当中的第i行包含两个整数xi,yi，代表点xi和点yi间有边相连。
输出描述
每个询问的回答占1行，若此图不是腰带图，该行里只包含一个整数-1；若是腰带图，则输出n个数p0,p1,...,pn-1，其为任一个能证明此图是腰带图的0~n-1的排列。(意思就是题面里提到的该有的边都存在。)
示例1
输入:
3 6 9 0 1 1 2 2 0 3 4 4 5 3 5 0 3 1 4 2 5 8 12 0 1 0 2 0 3 4 5 4 6 4 7 1 5 1 6 2 6 2 7 3 7 3 5 6 9 0 1 0 2 0 3 0 4 0 5 1 2 1 3 1 4 1 5
输出:
0 1 2 3 4 5 0 2 7 3 1 6 4 5 -1
C++11(clang++ 3.9) 解法, 执行用时: 26ms, 内存消耗: 1028K, 提交时间: 2018-03-03 21:13:11
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=220;
int n,m;
int can[N][N];
int vis[N],ans[N];
vector<int>E[N];
bool dfs(int x){
if(x==n/2){
for(int i=0;i<n;i++){
if(!can[ans[0]][ans[n/2-1]]||!can[ans[n/2]][ans[n-1]]) return 0;
printf("%d",ans[i]);
if(i!=n-1) printf(" ");
}
return 1;
}
if(!x){
vis[0]=1;
for(int i=0;i<E[x].size();i++){
int V=E[x][i];
vis[V]=1;
ans[n/2]=V;
if(dfs(x+1)) return 1;
vis[V]=0;
}
}
else{
for(int i=0;i<E[ans[x-1]].size();i++){
int V1=E[ans[x-1]][i];
if(vis[V1]) continue;
for(int j=0;j<E[ans[n/2+x-1]].size();j++){
int V2=E[ans[n/2+x-1]][j];
if(vis[V2]||!can[V1][V2]) continue;
vis[V1]=1;
vis[V2]=1;
ans[x]=V1;
ans[x+n/2]=V2;
if(dfs(x+1)) return 1;
vis[V2]=0;
vis[V1]=0;
}
}
}
return 0;
}
void Solve(){
for(int i=0;i<n;i++){
if(E[i].size()!=3){
cout<<-1;
return ;
}
}
if(!dfs(0)) cout<<-1;
}
int T;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) vis[i]=0,E[i].clear();
memset(can,0,sizeof(can));
for(int i=1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
E[a].pb(b);
E[b].pb(a);
can[a][b]=can[b][a]=1;
}
Solve();
cout<<endl;
}
return 0;
}