1491. 圆桌座位

1491. 圆桌座位

思路：

g数组存两个数字的关系，这里这样开辟bool数组确实好一点，比直接存关系要好，然后st数组维护每个数字是否别用过了，搜索顺序是每个位置，枚举的是可以放哪个人。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 15;
int pos[N];
bool st[N],g[N][N];
int n,m;

int dfs(int u){
    if(u == n){
        if(!g[pos[n - 1]][pos[0]]) return 1;
        return 0;
    }
    
    int res = 0;
    //搜索为位置可以放哪个人
    for(int i = 2; i <= n; i++){
        if(!st[i] && !g[i][pos[u - 1]]){
            st[i] = true;
            pos[u] = i;
            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;
}