Maximum Reachable Nodes — Problem Statement & Solution Guide
Problem Description
Consider a directed graph G = (V, E) where V is a set of N distinct nodes labeled from 0 to N-1, and E is a set of directed edges. The graph is provided as an adjacency list, where adj[i] contains the list of nodes j such that a directed edge exists from i to j. You are tasked with determining the maximum number of distinct nodes that can be visited in a single traversal starting from any node in the graph. A valid traversal follows the directed edges and may revisit nodes, but the count only includes unique nodes visited at least once. The goal is to find the starting node that maximizes this count and return that maximum count.
This problem requires identifying the node with the largest reachable set in a potentially cyclic directed graph. The solution involves analyzing the structure of the graph, particularly focusing on strongly connected components (SCCs) and the reachability between them. The maximum reachable nodes will be determined by the size of the union of all SCCs reachable from a given starting node, including the starting node's own SCC.
Input: An integer N representing the number of nodes, and a list of lists adj where adj[i] is a list of integers representing the nodes directly reachable from node i.
Output: An integer representing the maximum number of distinct nodes reachable from any single starting node.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Reachable Nodes"
WHY DOES IT MATTER?
The SCC + DAG DP pattern transforms a potentially cyclic, overlapping‑reachability problem into a clean hierarchical DP, turning exponential‑ish exploration into linear work. Mastery of this pattern unlocks efficient solutions for many reachability, influence‑maximization, and dependency‑resolution problems.
OPTIMIZATION CHALLENGE
The key insight is that nodes inside the same SCC share identical reachability sets; collapsing them eliminates redundant traversals and converts cycles into a DAG, enabling a single pass DP that aggregates component sizes.
REAL-WORLD CONNECTION
Think of a microservice architecture where services call each other. Services inside a tightly‑coupled loop (SCC) always invoke each other, so they can be treated as a single deployment unit. The call graph of these units is acyclic, letting ops compute the total downstream services impacted by a failure in linear time.
During an interview, first state the SCC condensation idea, then sketch Kosaraju’s two‑pass algorithm, and finally describe the DP recurrence. Keeping the explanation high‑level but precise shows you understand both theory and implementation.
COMPLEXITY AT A GLANCE
O(N + M)O(N + M)Core Theory — Why This Approach?
The problem asks for the largest set of distinct vertices reachable from any start vertex in a directed graph. A naïve solution would launch a depth‑first or breadth‑first search from every node, leading to O(N·(N+M)) time, which quickly becomes infeasible for large N and M. The optimal paradigm leverages two classic graph concepts: Strongly Connected Components (SCCs) and DP on a DAG. First, Kosaraju’s (or Tarjan’s) algorithm collapses each SCC—where every vertex can reach every other—into a single meta‑node, because any traversal that enters an SCC can visit all its members. The condensation graph is a Directed Acyclic Graph, allowing a single pass in topological order to compute, for each component, the total number of original nodes reachable from it (its own size plus the sizes of all downstream components). The maximum of these values across all components is the answer. This reduces the overall work to linear time O(N+M) and linear space, handling cycles gracefully while avoiding repeated traversals.
Interview Questions on This Problem
Q1How would you compute the maximum number of nodes reachable from any vertex in a directed graph that may contain cycles?
First find all SCCs using Kosaraju’s or Tarjan’s algorithm, compress them into a DAG, then perform DP in topological order where dp[comp] = size(comp) + sum of dp of all reachable downstream components (taking the maximum over outgoing edges). The answer is the maximum dp value across all components.
Q2Why is it insufficient to run a BFS/DFS from every node when N and M are up to 10^5?
Running BFS/DFS from each node would be O(N·(N+M)) in the worst case, which can be ~10^10 operations for N=10^5, far exceeding time limits. Overlapping sub‑problems (many nodes share large portions of reachable sub‑graphs) cause massive redundant work, which SCC condensation eliminates.
Q3Explain how the condensation of SCCs guarantees that the resulting graph is a DAG and why that property is crucial for the DP step.
By definition, an SCC has no outgoing edges that lead back to itself; any edge between two different SCCs must go from one component to another without forming a cycle, otherwise the two would belong to the same SCC. Hence the component graph is acyclic. This acyclicity allows us to process components in topological order, ensuring that when we compute dp[comp] all downstream dp values are already known.
Examples
Input
N = 4, adj = [[1], [2], [3], []]
Output
4
Explanation: Starting from node 0, the traversal visits 0 -> 1 -> 2 -> 3. All 4 nodes are visited. Starting from node 1, nodes 1, 2, 3 are visited (3 nodes). Starting from node 2, nodes 2, 3 are visited (2 nodes). Starting from node 3, only node 3 is visited (1 node). The maximum is 4.
Input
N = 5, adj = [[1, 2], [3], [3], [4], []]
Output
5
Explanation: Starting from node 0, the traversal can visit 0 -> 1 -> 3 -> 4 and 0 -> 2 -> 3 -> 4. The set of visited nodes is {0, 1, 2, 3, 4}, which has size 5. Starting from node 1, the set is {1, 3, 4} (size 3). Starting from node 2, the set is {2, 3, 4} (size 3). Starting from node 3, the set is {3, 4} (size 2). Starting from node 4, the set is {4} (size 1). The maximum is 5.
Input
N = 6, adj = [[1], [2], [0], [4], [5], [4]]
Output
3
Explanation: The graph has two components: a cycle 0->1->2->0 and a cycle 4->5->4. Starting from node 0, the reachable set is {0, 1, 2} (size 3). Starting from node 1, the reachable set is {1, 2, 0} (size 3). Starting from node 2, the reachable set is {2, 0, 1} (size 3). Starting from node 3, the reachable set is {3} (size 1). Starting from node 4, the reachable set is {4, 5} (size 2). Starting from node 5, the reachable set is {5, 4} (size 2). The maximum is 3.
Input
N = 7, adj = [[1, 2], [3], [4], [5], [6], [3], []]
Output
7
Explanation: Starting from node 0, the traversal can reach 0 -> 1 -> 3 -> 5 -> 3 (cycle) and 0 -> 2 -> 4 -> 6. The set of visited nodes is {0, 1, 2, 3, 4, 5, 6}, which has size 7. All other starting nodes have smaller reachable sets. The maximum is 7.
Constraints
- 1 <= N <= 10^5
- 0 <= adj[i][j] < N
- The graph may contain self-loops and multiple edges between the same pair of nodes.
- The total number of edges in the graph is at most 10^5.
- The graph is not necessarily connected.
Optimal Approach & Strategy
Compute SCCs, build the condensation DAG, then DP over the DAG in topological order to aggregate reachable node counts efficiently.
Brute Force Approach
Run a DFS/BFS from every vertex and record the number of distinct nodes visited; keep the maximum.
Verified Code Solutions
function solution(graph, start) { let visited = new Set(); function dfs(node) { if (visited.has(node)) return 0; visited.add(node); let count = 1; for (let neighbor of graph[node]) { count += dfs(neighbor); } return count; } return dfs(start); }class Solution { public: int solution(unordered_map<int, vector<int>>& graph, int start) { unordered_set<int> visited; return dfs(graph, start, visited); } private: int dfs(unordered_map<int, vector<int>>& graph, int node, unordered_set<int>& visited) { if (visited.find(node) != visited.end()) return 0; visited.insert(node); int count = 1; for (int neighbor : graph[node]) { count += dfs(graph, neighbor, visited); } return count; } }class Solution { public int solution(Map<Integer, List<Integer>> graph, int start) { Set<Integer> visited = new HashSet<>(); return dfs(graph, start, visited); } private int dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) { if (visited.contains(node)) return 0; visited.add(node); int count = 1; for (int neighbor : graph.get(node)) { count += dfs(graph, neighbor, visited); } return count; } }def solution(graph, start): visited = set() def dfs(node): if node in visited: return 0 visited.add(node) count = 1 for neighbor in graph[node]: count += dfs(neighbor) return count return dfs(start)function solution(graph, start) { let visited = new Set(); function dfs(node) { if (visited.has(node)) return 0; visited.add(node); let count = 1; for (let neighbor of graph[node]) { count += dfs(neighbor); } return count; } return dfs(start); }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.