题目描述
个人围坐一圈,有 M对朋友关系。
第 i对朋友关系是指,编号是 ai的人和编号是 bi的人是朋友。
现在要给他们安排座位,要求所有相邻的人不能是朋友。
问共有多少种方案?
如果两个方案只有旋转角度不同,则我们将其视为一种方案。
输入格式第一行包含两个整数 N,M。
接下来 M 行,每行包含一对 ai,bi。
输出格式
输出一个数,表示总方案数。
样例
输入样例1:
4 1
1 2
输出样例1:
2
输入样例2:
10 5
1 2
3 4
5 6
7 8
9 10
输出样例2:
112512
算法2
(dfs) $O(n^2)$
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N = 11;
int n, m;
int path[N];
bool mem[N][N],st[N];
int res;
void dfs(int x){//递归遍历所有位置
if(x == n){
if(mem[path[0]][path[n-1]]){//减去开头和结尾为朋友的情况
return;
}else{
//for(int i = 0; i < n; i++) cout<<path[i];
//cout<<endl;
res++;
return;
}
}
for(int i = 1; i<=n; i++){//遍历所有人
if(!st[i] && !mem[i][path[x-1]] ){
path[x] = i;
st[i] = true;
dfs(x+1);
st[i] = false;
}
}
}
int main(){
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
mem[a][b] = mem[b][a] =true;
}
//限定开头为1,减少了两个方案只有旋转角度不同的问题
//path[0] = 1, st[1] = true;
//dfs(1)
dfs(0);
cout<<res/n<<endl;//除以n也可以减少两个方案只有旋转角度不同的问题
}