Блог пользователя ss_96

doubt in implementation of DFS
Автор ss_96, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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]

→ Ответить