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.
- 1 \leq N \leq 10^5
- M \leq min (123456, N(N-1)/2)
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.
- 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.
- Time Complexity: O(N+M)
- Space Complexity: O(N+M) using an adjacency list
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