Help needed in Root the tree ( lunchtime September)

how to solve the problem root the tree

Not the question of cook off , it’s from lunchtime.

1 Like

ya i edited it thanks

Use the concept of in-degree. max in-degree of every node must be 1. If it is x for a particular node (x>1) ,make it 1 by changing the direction of (x-1) edges

topo sort + connected components

Do a topological sort on the nodes and create connected components starting from the first node in the topological sort.

Your answer is numberOfConnectedComponents - 1.

1 Like

if the occurrence of the to node is greater than 1 then add the (occurrence-1) to the result and finally finding it for all nodes print the result.

Just find the outdegree