Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- /* Use an adjacency list to store the tree. */
- vector < vector<int> > tree;
- /* This vector of integers stores the number
- of nodes in every 'subtree' of the main tree. */
- vector <int> subtreeNodeCount;
- /* This function uses recursion to perform a depth-first
- traversal of the whole tree starting from the root node,
- counting the number of nodes in each subtree. As it
- recurs, it fills the 'subtreeNodeCount' vector with its
- findings. */
- int Recur (int node) {
- /* Note that we consider a node to be
- a part of its own subtree, so every
- subtree in the tree has at least 1 node. */
- int curSum = 1;
- for (int i = 0 ; i < tree[node].size(); i++) {
- curSum += Recur (tree[node][i]);
- }
- return (subtreeNodeCount[node] = curSum);
- }
- int main () {
- /* Take the number of nodes and the number
- of edges in the tree from the input. */
- int N, M;
- cin >> N >> M;
- /* Use a loop to build the tree and the
- subtreeNodeCount array. */
- for (int i = 0; i < N; i++) {
- vector<int> node;
- tree.push_back(node);
- subtreeNodeCount.push_back(0);
- }
- /* Now we take each edge from input. */
- for (int i = 0; i < M; i++) {
- int u,v;
- cin >> u >> v;
- /* The input is 1-indexed, however we decrement
- every node index by 1 in order to make working
- with the 0-indexed vectors in C++ simpler. */
- u--;
- v--;
- /* In order to prevent the 'Recur' function from
- recurring back upwards through the tree, we ensure
- that all edges are unidirectional and pointing deeper. */
- int deepNode = max(u,v);
- int upperNode = min(u,v);
- tree[upperNode].push_back(deepNode);
- }
- /* Begin by calling the 'Recur' function at the root node. */
- Recur (0);
- /* The recursion is complete - we have filled the
- 'subtreeNodeCount' vector with the appropriate data,
- now, any subtree with an even number of nodes can
- be separated from the main tree by removing the edge
- connecting to its root. Therefore, we can increment
- the answer by 1 whenever we see a subtree of this nature. */
- int ans = 0;
- for (int i = 1; i < subtreeNodeCount.size(); i++) {
- if (subtreeNodeCount[i] % 2 == 0) {
- ans++;
- }
- }
- /* Output the final answer. */
- cout << ans << "\n";
- return 0;
- }
Add Comment
Please, Sign In to add comment