×

# GOOGOL03 - Editorial

 0 PROBLEM STATEMENT: Practice, Contest 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 code for more clarity on this concept) Author: Prayank Mathur Tester: Naman Taneja Editorialist: Prayank Mathur This question is marked "community wiki". asked 21 May '15, 16:25 6●3 accept rate: 0% 0★admin ♦♦ 19.0k●348●495●533
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,482
×1,114
×638
×292
×71
×3

question asked: 21 May '15, 16:25

question was seen: 1,126 times

last updated: 21 May '15, 18:03