"节点的度"指以该节点为端点的边的条数。"偶点"指度为偶数的节点。 给你一棵n个节点的有根树,节点标号为1~n,1号节点为根节点。特别的,每个点的子节点个数不超过5。 请你输出该树中偶点的个数。 输入 第一行一个整数n。 以后n行,每行若干个整数。第i行,第一个数为mi,表示节点i的子节点个数。紧接着mi个整数,表示节点i子节点的编号。保证父节点编号小于子节点。 输出 一行一个整数,表示偶点个数。c++代码
时间: 2024-04-15 20:28:46 浏览: 89
连通度与强正则图的2-可扩性 (1993年)
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<int> degrees;
vector<vector<int>> tree;
void dfs(int node) {
int degree = tree[node].size();
degrees[node] = degree;
for (int child : tree[node]) {
dfs(child);
}
}
int main() {
int n;
cin >> n;
tree.resize(n + 1);
degrees.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);
int evenCount = 0;
for (int i = 1; i <= n; i++) {
if (degrees[i] % 2 == 0) {
evenCount++;
}
}
cout << evenCount << endl;
return 0;
}
```
这段代码通过深度优先搜索(DFS)遍历树,计算每个节点的度,并统计偶点的个数。首先,我们定义了一个 `degrees` 数组来保存每个节点的度。然后,我们使用一个二维向量 `tree` 来表示树的结构,其中 `tree[i]` 表示节点 i 的子节点列表。在主函数中,我们首先读取输入数据,构建树的结构。然后,我们调用 `dfs` 函数开始深度优先搜索,从根节点开始遍历,并将每个节点的度记录在 `degrees` 数组中。最后,我们遍历 `degrees` 数组,统计偶点的个数并输出。
阅读全文