题目描述 "节点的度"指以该节点为端点的边的条数。"偶点"指度为偶数的节点。 给你一棵n个节点的有根树,节点标号为1~n,1号节点为根节点。特别的,每个点的子节点个数不超过5。 请你输出该树中偶点的个数。 输入 第一行一个整数n。 以后n行,每行若干个整数。第i行,第一个数为mi,表示节点i的子节点个数。紧接着mi个整数,表示节点i子节点的编号。保证父节点编号小于子节点。 输出 一行一个整数,表示偶点个数。 样例 输入 复制 3 2 2 3 0 0 输出 复制 1 请用c++解决
时间: 2024-04-16 16:23:46 浏览: 93
连通度与强正则图的2-可扩性 (1993年)
以下是用C++解决该问题的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 计算偶点的个数
int countEvenPoints(vector<vector<int>>& tree, int root) {
int count = 0;
// 获取当前节点的子节点个数
int numChildren = tree[root].size() - 1;
// 遍历子节点
for (int i = 1; i <= numChildren; i++) {
int child = tree[root][i];
// 递归计算子节点的偶点个数
int childCount = countEvenPoints(tree, child);
// 如果子节点是偶点,则当前节点也是偶点
if (childCount % 2 == 0) {
count++;
}
}
// 返回当前节点的偶点个数
return count + (numChildren % 2 == 0 ? 1 : 0);
}
int main() {
int n;
cin >> n;
vector<vector<int>> tree(n + 1);
// 构建树的结构
for (int i = 1; i <= n; i++) {
int m;
cin >> m;
tree[i].resize(m + 1);
tree[i][0] = m;
for (int j = 1; j <= m; j++) {
cin >> tree[i][j];
}
}
// 计算偶点的个数
int evenPoints = countEvenPoints(tree, 1);
// 输出结果
cout << evenPoints << endl;
return 0;
}
```
希望能对你有所帮助!如果还有其他问题,请随时提问。
阅读全文