easyGraphsPattern: DFS/BFS
Count Reachable Nodes in Undirected Graph Solution
Problem Statement
Given an undirected graph represented by an adjacency list and a starting node, return the total number of distinct nodes that can be reached from the starting node (inclusive). The graph consists of `n` nodes, labeled from `0` to `n-1`. The connections are provided as a list of edges, where each edge `[u, v]` indicates an undirected connection between node `u` and node `v`.
Examples
Example 1:
Input:{"n":5,"edges":[[0,1],[1,2],[3,4]],"startNode":0}
Output:3
Explanation: Starting from node 0, we can reach nodes 0, 1, and 2. Nodes 3 and 4 are in a separate component and cannot be reached. Therefore, the total count is 3.
Example 2:
Input:{"n":7,"edges":[[0,1],[0,2],[1,3],[4,5],[5,6]],"startNode":4}
Output:3
Explanation: Starting from node 4, we can reach nodes 4, 5, and 6. Nodes 0, 1, 2, and 3 are in a separate component. Therefore, the total count is 3.
Example 3:
Input:{"n":3,"edges":[[0,1],[1,2],[2,0]],"startNode":1}
Output:3
Explanation: The graph is fully connected. Starting from node 1, we can reach nodes 1, 0, and 2. Therefore, the total count is 3.
Constraints
- 1 <= n <= 10^5
- 0 <= edges.length <= 10^5
- 0 <= u, v < n
- u != v
- 0 <= startNode < n
Time: O(N + E) Space: O(N + E)
Use an adjacency list to represent the graph. Employ either BFS or DFS starting from the `startNode`. Maintain a set or boolean array to keep track of visited nodes. The size of the visited set/array at the end of the traversal is the answer.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from collections import deque
def count_reachable_nodes(n: int, edges: list[list[int]], start_node: int) -> int:
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
queue = deque([start_node])
visited[start_node] = True
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return count