• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
33%
SHARE
TWEET

# Even Tree [HackerRank]

a guest Jun 10th, 2017 2 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. using namespace std;
4.
5. /* Use an adjacency list to store the tree. */
6. vector < vector<int> > tree;
7. /* This vector of integers stores the number
8.    of nodes in every 'subtree' of the main tree. */
9. vector <int> subtreeNodeCount;
10. /* This function uses recursion to perform a depth-first
11.    traversal of the whole tree starting from the root node,
12.    counting the number of nodes in each subtree. As it
13.    recurs, it fills the 'subtreeNodeCount' vector with its
14.    findings. */
15. int Recur (int node) {
16.     /* Note that we consider a node to be
17.        a part of its own subtree, so every
18.        subtree in the tree has at least 1 node. */
19.     int curSum = 1;
20.     for (int i = 0 ; i < tree[node].size(); i++) {
21.         curSum += Recur (tree[node][i]);
22.     }
23.     return (subtreeNodeCount[node] = curSum);
24. }
25.
26. int main () {
27.     /* Take the number of nodes and the number
28.        of edges in the tree from the input. */
29.     int N, M;
30.     cin >> N >> M;
31.     /* Use a loop to build the tree and the
32.        subtreeNodeCount array. */
33.     for (int i = 0; i < N; i++) {
34.         vector<int> node;
35.         tree.push_back(node);
36.         subtreeNodeCount.push_back(0);
37.     }
38.     /* Now we take each edge from input. */
39.     for (int i = 0; i < M; i++) {
40.         int u,v;
41.         cin >> u >> v;
42.         /* The input is 1-indexed, however we decrement
43.            every node index by 1 in order to make working
44.            with the 0-indexed vectors in C++ simpler. */
45.         u--;
46.         v--;
47.         /* In order to prevent the 'Recur' function from
48.            recurring back upwards through the tree, we ensure
49.            that all edges are unidirectional and pointing deeper. */
50.         int deepNode = max(u,v);
51.         int upperNode = min(u,v);
52.         tree[upperNode].push_back(deepNode);
53.     }
54.
55.     /* Begin by calling the 'Recur' function at the root node. */
56.     Recur (0);
57.
58.     /* The recursion is complete - we have filled the
59.        'subtreeNodeCount' vector with the appropriate data,
60.        now, any subtree with an even number of nodes can
61.        be separated from the main tree by removing the edge
62.        connecting to its root. Therefore, we can increment
63.        the answer by 1 whenever we see a subtree of this nature. */
64.     int ans = 0;
65.     for (int i = 1; i < subtreeNodeCount.size(); i++) {
66.         if (subtreeNodeCount[i] % 2 == 0) {
67.             ans++;
68.         }
69.     }
70.
71.     /* Output the final answer. */
72.     cout << ans << "\n";
73.     return 0;
74. }
RAW Paste Data
Top