AcWing 1491. 圆桌座位
原题链接
简单
作者:
hayate
,
2024-05-02 00:47:56
,
所有人可见
,
阅读 2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11;
int n, m;
bool g[N][N], st[N];
int pos[N];
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;
for(int i = 0; i < m; i ++ )
{
int a, b;
cin >> a >> b;
g[a][b] = g[b][a] = true;
}
pos[0] = 1;
st[1] = true;
cout << dfs(1) << endl;
return 0;
}