从键盘输入图的邻接矩阵和一正整数m,计算结点两两之间长度为m的路的数目。考虑有向图和无向图。用C语言实现

以下是无向图的实现代码：

#include <stdio.h>

#define MAXN 100

int n; // 结点数
int m; // 路径长度
int adjMat[MAXN][MAXN]; // 邻接矩阵

int dfs(int u, int steps) {
    if (steps == m) { // 到达目标步数，返回1
        return 1;
    }
    int cnt = 0; // 计数器
    for (int v = 0; v < n; v++) {
        if (adjMat[u][v]) { // 如果u和v之间有边
            cnt += dfs(v, steps + 1); // 继续往下搜索
        }
    }
    return cnt;
}

int main() {
    // 输入结点数和邻接矩阵
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &adjMat[i][j]);
        }
    }
    // 输入路径长度
    scanf("%d", &m);
    // 枚举所有结点对
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += dfs(i, 0); // 从结点i开始搜索，步数为0
    }
    printf("路径长度为%d的路的数目为%d\n", m, cnt);
    return 0;
}

以下是有向图的实现代码：

#include <stdio.h>

#define MAXN 100

int n; // 结点数
int m; // 路径长度
int adjMat[MAXN][MAXN]; // 邻接矩阵

int dfs(int u, int steps) {
    if (steps == m) { // 到达目标步数，返回1
        return 1;
    }
    int cnt = 0; // 计数器
    for (int v = 0; v < n; v++) {
        if (adjMat[u][v]) { // 如果u指向v
            cnt += dfs(v, steps + 1); // 继续往下搜索
        }
    }
    return cnt;
}

int main() {
    // 输入结点数和邻接矩阵
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &adjMat[i][j]);
        }
    }
    // 输入路径长度
    scanf("%d", &m);
    // 枚举所有结点对
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += dfs(i, 0); // 从结点i开始搜索，步数为0
    }
    printf("路径长度为%d的路的数目为%d\n", m, cnt);
    return 0;
}