Need some hint. Please help.
I have solved it this way:
- Determine the bottom nodes of the tree (with no children)
- Assign "weight" 1 to each of the bottom nodes
- Build your way up the tree calculating the "weight" of each node (for example a node with 2 children has "weight" 3)
- Count the number of nodes with even "weight" excluding the root. That's your answer...
#include <iostream> #include <vector> using namespace std; struct Node{ int num,root; }; int main(){ int N,M;//nodes edges int x,y; int count = 0; cin >> N >> M; vector <Node> nodes = vector<Node>(N); for(int i = 0;i < N;i++){ nodes[i].num = 1; nodes[i].root = -1; } for(int i = 0;i < M;i++){ cin >> x >> y; nodes[x-1].root = y-1; } for(int i = N-1;i > 0;i--) if(nodes[i].root >= 0) nodes[nodes[i].root].num += nodes[i].num; for(int i = 0;i < N;i++) if(nodes[i].root >= 0 && nodes[i].num%2== 0) count ++; cout << count; return 0; }
I've seen huge walls of code down below, but this problem can be solved easily by taking advantage of how input data and problem constraints are set by the authors. Here's my simple C++ solution:
#include <bits/stdc++.h> using namespace std; struct node{ int parent, children = 0; }; int main(){ int n, o, p, result = 0; cin >> n >> o; vector<node> tree(n+1); while(cin >> o >> p){ tree[o].parent = p; tree[p].children++; } for(int i = n; i > 1; i--) if(tree[i].children%2){ tree[tree[i].parent].children--; result++; } cout << result; return 0; }
after breaking my head many hours (over the past week), I finally got all 9 test-cases cleared.
If you solved this in seconds, good on you, Congratulations. This comment is not for you, so please don't waste your time, reading further.
If you are having trouble getting your head-around, and are happy to spend few minutes reading this rather LENGTHY comment, proceed further, please.
There are test-cases with 80 vertices & 79 edges - so it is important to develop a generic solution.
What helped me most: [Apologies: though this is a graph and not a tree, it is easier for me to refer to nodes as child, parent, root and leaf. For example, edge 3-4 only connects nodes 3 and 4; however, for ease of understanding, I will call 3 as parent and 4 as child node. If a node has no child, it is leaf-node. If a node has no parent, it is root-node (in this case, 1 is always root-node)]
Algorithm-hint:
init: Initially, assign all nodes (including root, leaf, all) a "weight" of zero. Set 'counter' to zero.
step-1: Find all leaf-nodes.
step-2a: For each leaf-node, if weight is "even", add 1 to parent-node. Else [or, If weight is "odd"] add 1 to 'counter'. [explanation: if weight is odd, we break the edge from leaf-node to parent-node - hence increase counter.].
step-2b: Remove the leaf-node (from the tree/graph) and it's reference from it's parent (ie, the edge).
step-3: If leaf-nodes are empty or if 1 (ie, root-node) is present in leaf-nodes, proceed to next step. Else, repeat above steps (1, 2a, 2b).
step-4: Print counter - this is the number edges broken.
"getting leaf-nodes" --> based on your data-structure, you can get this. Given edges (on the input):
.
.
.
40 32
41 32
32 30
30 29
.
.
we can say 40, 41 are leaf-nodes "initially". Once steps 2a, 2b complete, these will be removed. Thus, 32 will become a leaf-node. Upon another iteration, 32 will be removed and 30 becomes a leaf-node... so on and so forth.
BTW: I found an online tree-generator to help visualize the tree.LaTreeX - online free TREE-PDF generator
Sort 263 Discussions, By:
Please Login in order to post a comment