题目描述 按如下方式定义"节点的深度": 1、 根节点的深度为0; 2、 若节点i是节点j的父节点,节点i的深度为di,则节点j的深度dj=di+1。 给你一棵n个节点的有根树,节点标号为1~n,1号节点为根节点。特别的,每个点的子节点个数不超过5。 请你输出这n个节点的深度。 输入 第一行一个整数n。 以后n行,每行若干个整数。第i行,第一个数为mi,表示节点i的子节点个数。紧接着mi个整数,表示节点i子节点的编号。保证父节点编号小于子节点。 输出 n个数,每行一个,依次为1~n号节点的深度。 样例 输入 3 2 2 3 0 0 输出 0 1 1 请用c++语言编码 头文件#include<bits/stdc++.h> using namespace std;
时间: 2024-04-15 14:32:07 浏览: 5
抱歉,我无法编写实际的代码或运行程序。但我可以为您提供一个解决方案的思路。
您可以使用深度优先搜索(DFS)来计算每个节点的深度。首先,您可以定义一个数组 `depth`,用于存储每个节点的深度。然后,从根节点开始进行DFS,并在遍历每个节点时,将其深度存储到 `depth` 数组中。
下面是一个可能的实现:
```cpp
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> tree;
vector<int> depth;
void dfs(int node, int d) {
depth[node] = d;
for (int child : tree[node]) {
dfs(child, d + 1);
}
}
int main() {
int n;
cin >> n;
tree.resize(n + 1);
depth.resize(n + 1);
for (int i = 1; i <= n; i++) {
int m;
cin >> m;
for (int j = 0; j < m; j++) {
int child;
cin >> child;
tree[i].push_back(child);
}
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
cout << depth[i] << endl;
}
return 0;
}
```
希望这个思路可以帮助到您!