mediumGraphsPattern: DFS
Find Reachable Nodes from Multiple Sources Solution
Problem Statement
Given an undirected graph represented by an adjacency list `adj` and a list of integer `sources`, return the count of all nodes that are reachable from any node in the `sources` list. A node is reachable if there is a path from any of the source nodes to it. The graph can contain cycles.
Examples
Example 1:
Input:adj = [[1, 2], [0, 3], [0], [1]], sources = [0]
Output:4
Explanation: Starting from node 0, we can reach nodes 1 and 2. From node 1, we can reach node 3. Therefore, all nodes {0, 1, 2, 3} are reachable.
Example 2:
Input:adj = [[1], [0, 2], [1], [4], [3]], sources = [0, 3]
Output:5
Explanation: From source 0, we can reach {0, 1, 2}. From source 3, we can reach {3, 4}. Combining these, all nodes {0, 1, 2, 3, 4} are reachable.
Example 3:
Input:adj = [[1], [0], [3], [2]], sources = [0, 2]
Output:4
Explanation: From source 0, we reach {0, 1}. From source 2, we reach {2, 3}. All nodes {0, 1, 2, 3} are reachable.
Constraints
- The number of nodes `N` in the graph is between 1 and 10^5.
- The number of edges `E` is between 0 and 2*10^5.
- The `sources` list contains between 1 and `N` nodes.
- Each element in `adj` and `sources` is an integer between 0 and `N-1`.
- The graph is undirected. If `u` is in `adj[v]`, then `v` is in `adj[u]`.
Time: O(V + E) Space: O(V)
Initialize a queue or stack for BFS/DFS and a set to keep track of visited nodes. Add all source nodes to the queue/stack and the visited set. Then, perform a standard BFS or DFS. Explore neighbors of nodes currently in the queue/stack. If a neighbor hasn't been visited, add it to the queue/stack and the visited set. The size of the visited set at the end is the count of reachable nodes.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def find_reachable_nodes(adj, sources):
n = len(adj)
visited = set()
for source in sources:
dfs(adj, source, visited)
return len(visited)
def dfs(adj, u, visited):
if u not in visited:
visited.add(u)
for v in adj[u]:
dfs(adj, v, visited)