原題鏈接：請點擊我

思路：把樹還原出來，對每個結點，計算以該結點為根的子樹結點數。子樹結點數為偶數的結點數量就是所求森林中樹木的數量。結點數量減去一就是所求結果。

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std;struct node{int index, num_subtree;vector<node*> children;node(int i=0,int n=0):index(i),num_subtree(n), children(vector<node*>()){} };node* construct_tree(int parent, int index, const vector<vector<int>>& adjLsit); void count_even(node* root, int& cnt);int main() {/* Enter your code here. Read input from STDIN. Print output to STDOUT */int N, M; cin >> N >> M;vector<vector<int>> adjList(N + 1);for(int i = 0; i < M; i++){int n1, n2; cin >> n1 >> n2;adjList[n1].push_back(n2);adjList[n2].push_back(n1);}node* root = construct_tree(0, 1, adjList);int cnt = 0;count_even(root, cnt);cout << cnt - 1 << endl;return 0; }node* construct_tree(int parent, int index, const vector<vector<int>>& adjList){node* tmp = new node(index);tmp->num_subtree = 1;for(int i = 0; i < adjList[index].size(); i++){if(adjList[index][i] != parent){tmp->children.push_back(construct_tree(index, adjList[index][i], adjList));tmp->num_subtree += tmp->children.back()->num_subtree;}}return tmp; }void count_even(node* root, int& cnt){for(auto vit: root->children){count_even(vit, cnt);}if(root->num_subtree%2==0){cnt++;} }

?

總結

以上是生活随笔為你收集整理的Hacker Rank 上的 Even Tree 小议的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。