We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Even Tree
You are viewing a single comment's thread. Return to all comments →
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