mediumGraphsPattern: BFS
Minimum Time to Reach All Vertices Solution
Problem Statement
You are given an undirected graph represented by an adjacency list `adj`, where `adj[i]` contains a list of `i`'s neighbors. You are also given a `source` node. A message is sent from the `source` node and propagates simultaneously along all connected edges. It takes one unit of time for the message to traverse a single edge. Determine the minimum total time required for the message to reach *all* nodes in the graph. If it is impossible to reach all nodes from the given `source`, return -1.
Examples
Example 1:
Input:adj = [[1], [0,2], [1]], source = 0
Output:2
Explanation: Nodes are 0, 1, 2. Source is 0.
Time 0: Message at node 0.
Time 1: Message reaches node 1 (from 0). Nodes covered: {0, 1}.
Time 2: Message reaches node 2 (from 1). Nodes covered: {0, 1, 2}.
All 3 nodes are covered. The maximum time taken for any node to be reached is 2 units.
Example 2:
Input:adj = [[1], [0], [3], [2]], source = 0
Output:-1
Explanation: Nodes are 0, 1, 2, 3. Source is 0.
From source 0, the message can reach node 1 (at time 1).
Nodes 2 and 3 are in a separate connected component and are unreachable from node 0. Since not all nodes in the graph (0, 1, 2, 3) can be reached, the result is -1.
Example 3:
Input:adj = [[]], source = 0
Output:0
Explanation: There is only one node, 0, which is the source. All nodes are covered at time 0.
Constraints
- 1 <= n <= 10^5 (Number of nodes)
- 0 <= sum(adj[i].length) <= 2 * 10^5 (Total number of edges, roughly 'm')
- 0 <= source < n
- The graph is undirected.
- Nodes are labeled from 0 to n-1.
Time: O(V + E) Space: O(V)
The optimal approach leverages Breadth-First Search (BFS) to efficiently determine the minimum time to reach each node from the source. BFS explores the graph layer by layer, naturally finding the shortest path (in terms of edges) to all reachable nodes. We track the maximum distance encountered during the traversal; this maximum represents the total time, provided all nodes are reachable.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
from collections import deque
def solve():
n = int(sys.stdin.readline())
adj = [[] for _ in range(n)]
for i in range(n):
line = sys.stdin.readline().strip()
if line: # Handle empty lines for nodes with no neighbors
neighbors = list(map(int, line.split()))
adj[i].extend(neighbors)
source = int(sys.stdin.readline())
dist = [-1] * n
q = deque()
dist[source] = 0
q.append(source)
nodes_reached = 1
max_time = 0
while q:
u = q.popleft()
max_time = max(max_time, dist[u])
for v in adj[u]:
if dist[v] == -1: # If unvisited
dist[v] = dist[u] + 1
q.append(v)
nodes_reached += 1
if nodes_reached != n:
print(-1)
else:
print(max_time)
solve()