题目描述 "节点的度"指以该节点为端点的边的条数。"偶点"指度为偶数的节点。 给你一棵n个节点的有根树,节点标号为1~n,1号节点为根节点。特别的,每个点的子节点个数不超过5。 请你输出该树中偶点的个数。 输入 第一行一个整数n。 以后n行,每行若干个整数。第i行,第一个数为mi,表示节点i的子节点个数。紧接着mi个整数,表示节点i子节点的编号。保证父节点编号小于子节点。 输出 一行一个整数,表示偶点个数。 样例 输入 复制 3 2 2 3 0 0 输出 复制 1c++代码
时间: 2024-04-15 17:30:49 浏览: 84
三条邮路的图形如图所示-图论中几个典型问题的求解
对于这个问题,我们可以使用深度优先搜索(DFS)来遍历整棵树。在遍历的过程中,我们可以记录每个节点的度数,并统计偶点的个数。
下面是使用C++语言实现的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> tree;
vector<int> degree;
int evenCount = 0;
void dfs(int node) {
for (int i = 0; i < tree[node].size(); i++) {
int child = tree[node][i];
degree[node]++;
degree[child]++;
dfs(child);
}
if (degree[node] % 2 == 0) {
evenCount++;
}
}
int main() {
int n;
cin >> n;
tree.resize(n + 1);
degree.resize(n + 1, 0);
for (int i = 2; i <= n; i++) {
int parent;
cin >> parent;
tree[parent].push_back(i);
}
dfs(1);
cout << evenCount << endl;
return 0;
}
```
希望对你有所帮助!如果有任何问题,请随时提问。
阅读全文