JVPHOBIA - EDITORIAL

general
, , , ,
1

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 :slight_smile:

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