N 个人围坐一圈,有 M
对朋友关系。
第 i
对朋友关系是指,编号是 ai 的人和编号是 bi
的人是朋友。
现在要给他们安排座位,要求所有相邻的人不能是朋友。
问共有多少种方案?
如果两个方案只有旋转角度不同,则我们将其视为一种方案。
输入格式
第一行包含两个整数 N,M
。
接下来 M
行,每行包含一对 ai,bi
。
输出格式
输出一个数,表示总方案数。
数据范围
3≤N≤10
,
0≤M≤N(N−1)2,
1≤ai<bi≤N,
(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
整体思路:
按题目要求输入n个人,m个互相认识的情况,按题中要求,认识的人不能挨着,问有多少种方案
首先,定义pos[N]表示pos[i]个座位坐的是哪个人,str[N]表示人有没有被用过,g[N][N]表示两个人是否认识
从第一个人开始,所以设第一个人已经用过,并且第一个位置坐的是1
接下来是dfs思路
dfs传入一个参数表示到了第几个位置
如果位置等于人数,就说明已经坐满,这时要考虑最后一个人是否与第一个人是朋友关系,如果不是朋友关系,说明这个方案成立,就返回1,如果是朋友关系,就说明该方案不成立,就返回0
接下来是dfs主体部分思路
从1-n个人依次遍历,条件是这个人没用过且这个人与上一个人不是朋友,如果满足以上条件,就让这个人坐在这个座位上,并且备注他已经被用过,然后进行下一个位置的搜索,执行完dfs[u+1]要进行还原现场,把这个人改为没用过
执行完n个人的所有情况以后,得出来的res就是该题答案,最后返回res
题解代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int m;
bool g[N][N];
int pos[N];
bool str[N];
int dfs(int u)
{
if(u==n)
{
if(g[pos[0]][pos[u-1]]) return 0;
return 1;
}
int res = 0;
for(int i =1;i<=n;i++)
{
if(!str[i]&&!g[i][pos[u-1]])
{
str[i] = true;
pos[u] = i;
res+=dfs(u+1);
str[i] = false;
}
}
return res;
}
int main()
{
cin>>n>>m;
while(m–)
{
int a,b;
cin>>a>>b;
g[a][b] = true;
g[b][a] = true;
}
str[1] = true;
pos[0] = 1;
cout<<dfs(1)<<endl;
return 0;
}