7-78 散步

最近HY喜欢上了散步。HY住在南山校区，他发现南山校区有n个景点（从1到n进行编号）很值得观赏，比如竹林舞步，小河夕阳等。HY不想错过每个景点，但又不想在一次散步过程中经过任意一个景点超过一次。HY的散步方案要求是从住所（设编号为0）出发，经过每个景点有且仅有一次，最后回到住所。你能告诉他满足要求的方案总数是多少吗？

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据首先输入1个整数n（1≤n<10），然后有n行输入。第i行先输入一个整数mi（1≤mi?≤n），然后是mi?个整数，表示从景点i所能直达的景点（也可以是住所）编号。当然，若景点1能直达景点2，则景点2同样也能直达景点1。

输出格式:

对于每组测试，在一行上输出满足HY的散步方案要求的方案总数。

输入样例:

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

输出样例:

2
0
4

出处：

[1] 黄龙军, 等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
[2] 黄龙军, 等. 数据结构与算法（Python版）,上海: 上海交通大学出版社, 2023. ISBN: 9787313280732

?

#include <stdio.h>
#include <stdbool.h>

#define MAX_N 10

// 深度优先搜索函数
int dfs(int graph[MAX_N][MAX_N], bool visited[MAX_N], int current, int num_visited, int total_nodes) {
    // 如果所有景点都已经访问过，并且回到起点，则找到一种方案
    if (num_visited == total_nodes) {
        if (graph[current][0]) { // 返回到起点0，完成一次散步
            return 1;
        }
        return 0; // 没有有效的散步方案
    }

    int count = 0;
    visited[current] = true; // 将当前景点标记为已访问

    for (int i = 0; i < total_nodes; i++) {
        // 如果当前景点与i景点相连，并且i景点尚未访问，则继续搜索
        if (graph[current][i] && !visited[i]) {
            count += dfs(graph, visited, i, num_visited + 1, total_nodes);
        }
    }

    visited[current] = false; // 回溯，将当前景点标记为未访问
    return count;
}

// 找到满足要求的散步方案总数
int find_walks(int graph[MAX_N][MAX_N], int n) {
    int total_nodes = n + 1;
    bool visited[MAX_N] = {false};

    visited[0] = true; // 从景点0（住所）开始
    return dfs(graph, visited, 0, 1, total_nodes);
}

int main() {
    int T, n;
    scanf("%d", &T); // 输入测试用例的数量

    while (T--) {
        scanf("%d", &n); // 输入当前测试用例中景点的数量
        int graph[MAX_N][MAX_N] = {0};
        int m, v;

        // 输入景点之间的直达关系
        for (int i = 1; i <= n; i++) {
            scanf("%d", &m); // 输入从景点i直接能到达的景点数量
            for (int j = 0; j < m; j++) {
                scanf("%d", &v); // 输入能直接到达的景点编号
                graph[i][v] = 1; // 将景点i和v连接起来
                graph[v][i] = 1; // 将景点v和i连接起来（因为是双向的）
            }
        }

        printf("%d\n", find_walks(graph, n)); // 输出满足要求的散步方案总数
    }

    return 0;
}

?