AcWing 1491. 圆桌座位
原题链接
简单
作者:
continue_8
,
2024-04-01 22:05:45
,
所有人可见
,
阅读 5
#include<iostream>
using namespace std;
const int N=11;
bool g[N][N],st[N];
int pos[N]; //表示每个位置上的人
int n,m;
int dfs(int u){
if(u==n){
if(g[pos[0]][pos[n-1]]) return 0;
else return 1;
}
int res=0;
for(int i=1;i<=n;i++){
if(!st[i]&&!g[i][pos[u-1]]){
pos[u]=i;
st[i]=true;
res+=dfs(u+1);
st[i]=false;
}
}
return res;
}
int main(){
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
g[a][b]=g[b][a]=true;
}
pos[0]=1; //第一个人坐上去
st[1]=true; //或st[pos[0]]=true
cout<<dfs(1)<<endl;;
return 0;
}