ACWing 1491. 圆桌座位（dfs）

1491. 圆桌座位 - AcWing题库

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

第 i𝑖 对朋友关系是指，编号是 ai𝑎𝑖 的人和编号是 bi𝑏𝑖 的人是朋友。

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

问共有多少种方案？

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

输入格式

第一行包含两个整数 N,M𝑁,𝑀。

接下来 M𝑀 行，每行包含一对 ai,bi𝑎𝑖,𝑏𝑖。

输出格式

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

数据范围

3≤N≤103≤𝑁≤10,
0≤M≤N(N−1)20≤𝑀≤𝑁(𝑁−1)2,
1≤ai<bi≤N1≤𝑎𝑖<𝑏𝑖≤𝑁,
(ai,bi)≠(aj,bj)(𝑎𝑖,𝑏𝑖)≠(𝑎𝑗,𝑏𝑗),
所有输入均为整数。

输入样例1：

4 1
1 2

输出样例1：

2

输入样例2：

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

输出样例2：

112512

/*
要求所有相邻的人不能是朋友的排位为情况有几种。
先固定一个1，然后枚举安排剩下的人，当枚举完后，再检查最后一个人与第一个人是不是朋友

*/

#include<iostream>

using namespace std;

const int N = 15,M = 50;

bool g[N][N],st[N]; //g[i][j] i 和 j是朋友的话为true，st[i] 检查当前的人有么有用给过
int pos[N]; //记录每个人的位置
int n,m;

int dfs(int u)
{
    if(u - 1 == n)  //当所有人枚举完后，检查最后一个人与第一个人是不是朋友
    {
        if(g[pos[n]][pos[1]])
            return 0;
        return 1;
    }
    
    int res = 0;
    
    for(int i = 2;i<=n;i++) 
    {
        if(!st[i] && !g[i][pos[u - 1]])     //当前人没有用过，并且与前一个人不是朋友，那么第u个位置为i
        {
            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;        //i和j j和i是一样的
    }
    
    pos[1] = 1;
    st[1] = true;   //第一个人先固定
    
    cout <<dfs(2);  //从第二个人开始进行枚举
    return 0;
}

ps:dfs搜索的是第i给位置上是谁，也就是所在枚举所有人的时候要保证当前的人没有被用过并且与前一位已经安排好的人不是朋友，这样才能坐到相邻

挑战模式