从键盘输入图的邻接矩阵和一正整数m,计算结点两两之间长度为m的路的条数。简单C语言
时间: 2024-03-26 08:40:40 浏览: 17
好的,以下是计算结点两两之间长度为m的路的条数的简单C语言代码,可以参考一下:
```c
#include <stdio.h>
#define MAXN 1000
int G[MAXN][MAXN]; // 图的邻接矩阵
int n; // 结点数
int main() {
int m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &G[i][j]);
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) { // 只计算一次
int cnt = 0;
for (int k = 0; k < n; ++k) {
if (G[i][k] && G[k][j]) {
++cnt;
}
}
if (cnt >= m) {
++ans;
}
}
}
printf("%d\n", ans);
return 0;
}
```
这个代码的思路是,对于每一对结点(i, j),枚举中间结点k,计算i到k和k到j之间是否存在边,如果存在,则长度为m的路径的条数加1。最后输出所有长度为m的路径的条数之和即可。
需要注意的一点是,由于是无向图,所以计算出来的数量会有重复的情况,因此需要只计算一次,即j从i+1开始枚举。