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

×

JVPHOBIA - EDITORIAL

PROBLEM LINK:

Practice
Contest

Setter: Jayprakash Mahto
Tester: Jayprakash Mahto, Taranpreet Singh
Editorialist: Akash Bhalotia

DIFFICULTY:

EASY

PREREQUISITES:

DFS

PROBLEM:

Given an undirected weighted graph with N nodes and M edges. K nodes are initially reachable. A node is reachable from another reachable node if their edge weight is $\leq$ S. Find out how many nodes are reachable.

CONSTRAINTS:

  • 1 $\leq$ N $\leq$ $10^5$
  • M $\leq$ min (123456, N(N-1)/2)

QUICK EXPLANATION:

Run a DFS from each reachable node. If any neighbour has edge weight $\leq$ S, it is reachable and run a DFS from it. Maintain a visited array so that you visit each node atmost once. Print the number of nodes that were visited.

EXPLANATION:

  • We simply need to traverse the graph and find out which nodes are reachable. Let's do this using Depth-First Search.
  • Initially, K nodes are reachable. We'll run a DFS from each one of them.
  • Once we have run DFS from a node, we don't gain anything by running a DFS through it again. Hence, we'll maintain an array visited[] and marked a node as visited before running DFS from it.
  • If a neighbour of a reachable node has an edge weight $\leq$ S with it, it too is reachable. Thus, we will add it to the DFS stack and mark it as visited. We'll keep doing this till we have run a DFS on all nodes which are reachable.
  • Note that we only visit nodes which are reachable. Thus, the answer is the number of nodes marked as visited in the visited array.
  • This works even when the graph is disconnected as we check for every edge of a node.

COMPLEXITY:

  • Time Complexity: O(N+M)
  • Space Complexity: O(N+M) using an adjacency list

AC SOLUTIONS:

SIMILAR PROBLEMS:


Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :)

Thanks to @taran_1407 and @vijju123 for their constant guidance and support.

This question is marked "community wiki".

asked 26 Jan, 19:06

akashbhalotia's gravatar image

4★akashbhalotia
68112
accept rate: 14%

edited 26 Jan, 19:09

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:

×3,767
×726
×177
×31
×28

question asked: 26 Jan, 19:06

question was seen: 138 times

last updated: 26 Jan, 19:09