You are not logged in. Please login at www.codechef.com to post your questions!

×

GOOGOL03 - Editorial

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

surajjumpy's gravatar image

2★surajjumpy
62
accept rate: 0%

edited 21 May '15, 18:03

admin's gravatar image

0★admin ♦♦
17.4k347487515

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×12,340
×967
×474
×255
×52
×3

question asked: 21 May '15, 16:25

question was seen: 955 times

last updated: 21 May '15, 18:03