Lecture 4: round table seats

subject ：AcWing 1491. Round table seats
N I'll sit around , Yes M To friends .

The first i To a friend relationship means , The number is a_i The person and number of is b_i People are friends .

Now we have to arrange seats for them , Ask all the neighbors not to be friends .

Ask how many schemes there are ？

If the two schemes only have different rotation angles , Then we regard it as a plan .

Input format
The first line contains two integers N,M.

Next M That's ok , Each line contains a pair a_i,b_i.

Output format
Output a number , Represents the total number of schemes .

Data range

sample input 1：

4 1
1 2

sample output 1：

2

sample input 2：

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

sample output 2：

112512

Topic analysis ：
First of all to see N The scope of is very small , Therefore, violent search is generally used
Because equality after rotation is also regarded as the same scheme , So we fixed the first one as 1.（ The key ）
And finally we use DFS Just search , Remember to look back .

#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;
}