### PROBLEM LINK:

**Setter:** Jayprakash Mahto

**Tester:** Jayprakash Mahto, Taranpreet Singh

**Editorialist:** Akash Bhalotia

### DIFFICULTY:

EASY

### PREREQUISITES:

### 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.