题目描述

N 个人围坐一圈，有 M 对朋友关系。

第 i 对朋友关系是指，编号是 a[i] 的人和编号是 b[i] 的人是朋友。

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

问共有多少种方案？

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

样例

输入:
4 1
1 2
输出：
2

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

const int N = 11;
int n,m;
bool g[N][N], st[N];//g表示朋友关系，st表示人是否使用过的状态
int pos[N];//每个位置上是谁;

int dfs(int u)
{
    if(u==n)//表示排满了n个人
    {
        if(g[pos[n-1]][pos[0]]) return 0;
        return 1;
    }
    int res = 0;//统计有几种方案
    for(int i =1 ; i<=n ;i++){
        if(!g[i][pos[u-1]]&&!st[i])//该人没有用过并且与前一个人（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;//表示第一个人已经使用

    cout<<dfs(1)<<endl;

    return 0;
}