输入一棵有向树,输出每个结点所在的层数。输入格式 第一行输入结点个数n,第二行开始起输入n个结点对应的邻接矩阵。 输出格式 输出n行,每行按字典顺序直接输出每个结点的层数,如根结点是0,第一层结点是1等。Dev-c++5.11c语言代码实现
时间: 2024-02-25 09:58:12 浏览: 137
以下是Dev-c++5.11c语言代码实现:
```c
#include <stdio.h>
#include <string.h>
#define MAXN 1005
int n, level[MAXN];
int graph[MAXN][MAXN], visited[MAXN];
void dfs(int u, int dep) {
level[u] = dep;
visited[u] = 1;
for (int i = 1; i <= n; i++) {
if (graph[u][i] && !visited[i]) {
dfs(i, dep + 1);
}
}
}
int main() {
memset(graph, 0, sizeof(graph));
memset(visited, 0, sizeof(visited));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &graph[i][j]);
}
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i, 0);
}
}
for (int i = 1; i <= n; i++) {
printf("%d\n", level[i]);
}
return 0;
}
```
首先定义了一个`MAXN`常量表示结点个数的最大值,在这里设为1005。
然后定义了变量`n`表示结点个数,数组`graph`表示邻接矩阵,数组`visited`表示结点是否被访问过,数组`level`表示每个结点所在的层数。
接着定义了`dfs`函数进行深度优先搜索,其中`u`表示当前结点,`dep`表示当前结点所在的层数,每次递归都将当前结点的层数赋值给`level`数组,并将当前结点标记为已访问。然后遍历当前结点的所有邻接结点,若该邻接结点未被访问,则以该邻接结点作为新的起点继续进行深度优先搜索。
在`main`函数中,首先对邻接矩阵`graph`和访问数组`visited`进行初始化,然后从输入中读入结点个数和邻接矩阵。接着对每个未被访问的结点进行深度优先搜索,并将搜索结果存储在`level`数组中。最后按字典顺序输出每个结点的层数。
需要注意的是,在这里的层数是从0开始计算的,即根结点的层数为0,第一层结点的层数为1。
阅读全文