题目
个人围坐一圈，有 对朋友关系。
第 对朋友关系是指，编号是 的人和编号是 的人是朋友。
现在要给他们安排座位，要求所有相邻的人不能是朋友。
问共有多少种方案？
如果两个方案只有旋转角度不同，则我们将其视为一种方案。
输入格式
第一行包含两个整数 。
接下来 行，每行包含一对 。
输出格式
输出一个数，表示总方案数。
数据范围
,
,
,
,
所有输入均为整数。
输入样例1：
4 1
1 2
输出样例1：
2
输入样例2：
10 5
1 2
3 4
5 6
7 8
9 10
输出样例2：
112512
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
using namespace std;
const int N = 11;
int n, m;
int pos[N];
bool g[N][N], st[N];
int dfs(int u)
{
if (u == n) return !g[pos[u - 1]][1];
int res = 0;
for (int i = 1; i <= n; ++ i)
if (!st[i] && !g[pos[u - 1]][i])
{
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;
}
|
首先要考虑递归结束条件，保存状态，还原状态
今天脑子还是生锈状态。。。
