PROBLEM STATEMENT: [Practice][1], [Contest][2]
CATEGORY: EASY-MEDIUM
PRE-REQUISITES: Depth First Search, Minimum Spanning Tree, Graph.
EXPLAINATION:
From the statement marked bold it was clear that you had to create a minimum spanning tree from the initial given graph.
Now using DFS we can calculate how many total numbers of nodes a particular node is connected to. This is done by choosing any node as a parent and then recursively calculating it.
Once this is done, to calculate the busyness for every node, we know that any particular node is connected to n-1 other nodes (directly or indirectly, because it was a connected graph). Also we know the adjacently connected nodes of a given node. Therefore, starting from any adjacent node we multiply its connectivity with the remaining number of nodes. Doing this for all the adjacent nodes will give you the final busyness for a particular node. (See the
[3] for more clarity on this concept)
**Author:** [Prayank Mathur][4]</br>
**Tester:** [Naman Taneja][5]</br>
**Editorialist:** [Prayank Mathur][6]
[1]: http://www.codechef.com/problems/GOOGOL03
[2]: http://www.codechef.com/GOOG2015/problems/GOOGOL03
[3]: http://ideone.com/IJTq27
[4]: http://www.codechef.com/users/codingstar
[5]: http://www.codechef.com/users/na1taneja2821
[6]: http://www.codechef.com/users/codingstar