第四讲：圆桌座位

题目：AcWing 1491. 圆桌座位
N 个人围坐一圈，有 M 对朋友关系。

第 i 对朋友关系是指，编号是 a_i 的人和编号是 b_i 的人是朋友。

现在要给他们安排座位，要求所有相邻的人不能是朋友。

问共有多少种方案？

如果两个方案只有旋转角度不同，则我们将其视为一种方案。

输入格式
第一行包含两个整数 N,M。

接下来 M 行，每行包含一对 a_i,b_i。

输出格式
输出一个数，表示总方案数。

数据范围

输入样例1：

4 1
1 2

输出样例1：

2

输入样例2：

10 5
1 2
3 4
5 6
7 8
9 10

输出样例2：

112512

题目分析：
首先看到N的范围很小，所以一般会使用暴力搜索
因为旋转过后相等也视为同一种方案，所以我们固定第一个为1。（关键）
最后我们使用DFS进行搜索即可，记得回溯一下。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 15;
int g[N][N];
int st[N];
int choose[N];
int res=0;
int n,m;

void dfs(int k)
{
    
    if(k==n)
    {
    
        if(g[choose[0]][choose[n-1]]==0)res++;
        return;
    }
    
    for(int i=2;i<=n;i++)
    {
    
        if(!st[i]&&!g[choose[k-1]][i])
        {
    
            choose[k]=i;
            st[i]=1;
            dfs(k+1);
            st[i]=0;
        }
    }
}
int main()
{
    
    cin>>n>>m;
    while(m--)
    {
    
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }
    
    st[1]=1;
    choose[0]=1;
    dfs(1);
    cout<<res<<endl;
    return 0;
}