P1657 选书

时间限制 1.00s 内存限制 125.00MB

题目描述

学校放寒假时，信息学奥赛辅导老师有1,2,3……x本书，要分给参加培训的x个人，每人只能选一本书，但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。

输入格式

第1行：一个数x

第2行~第1+x行：每行两个数，表示ai喜欢的书的序号

输出格式

只有一个数：总方案数total。

输入输出样例

输入 #1

5 1 3 4 5 2 5 1 4 3 5

输出 #1

2

输入数据范围考虑清楚，尤其是0哦！

//选书 //算法：dfs //参数：n //n 记录第几个人选 #include<bits/stdc++.h> using namespace std; int x, a[25][2], num, visited[25]; void dfs (int n) { if (n == x+1) { num++; return; } for (int i = 0; i < 2; i++) { if (visited[a[n][i]]) continue; visited[a[n][i]] = 1; dfs(n+1); visited[a[n][i]] = 0; } return; } int main () { scanf("%d", &x); for (int i = 1; i <= x; i++) scanf("%d%d", &a[i][0], &a[i][1]); if (!x) printf("0"); else { dfs(1); printf("%d", num); } return 0; }