Guest User

Even Tree [HackerRank]

a guest
Jun 10th, 2017
22
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment