ss_96's blog

By ss_96, history, 7 years ago, In English

I was trying to solve a simple DFS question and my code was not passing 2 test cases.

Question:link The solution is also given in the first comment of the problem. Can anyone please explain why the check variable is used in that code.

Thanks.

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Check is used to differentiate between root's children and other node's children. The number of children of root is equal to number of nodes connected to root but in other nodes, number of children is 1 less than number of nodes connected to it. For root children, comparison should be like no_of_nodes_connected[root]<no_of_nodes_connected[child]-1 but for other node's children, no_of_nodes_connected[other_node]-1<no_of_nodes_connected[child]-1 which is equivalent to no_of_nodes_connected[other_node]<no_of_nodes_connected[child]