How do you solve Count Visited Nodes in a Directed Graph on LeetCode?

Count Visited Nodes in a Directed Graph (LeetCode #2876) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The graph contains at least one cycle, which is crucial for understanding node visits.

What is the brute force solution for Count Visited Nodes in a Directed Graph?

The brute force approach for Count Visited Nodes in a Directed Graph is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves starting from each node and performing a depth-first search (DFS) to count the unique nodes visited until a cycle is detected. This method is straightforward but inefficient for larger graphs. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Count Visited Nodes in a Directed Graph?

Clearly explain your thought process and approach before coding. Consider edge cases, such as nodes that lead directly to cycles. Discuss the trade-offs between brute force and optimized solutions during the interview.

What are common mistakes when solving Count Visited Nodes in a Directed Graph?

Not handling cycles correctly, leading to infinite loops. Failing to use memoization, resulting in excessive recomputation.

#2876

Count Visited Nodes in a Directed Graph

Hard

Dynamic ProgrammingDepth-First SearchGraph TheoryTopological SortMemoizationDepth-First SearchMemoizationGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages the fact that the graph contains cycles, allowing us to use memoization and a single DFS traversal to efficiently compute the number of unique nodes visited from each starting node.

⚙️

Algorithm

3 steps

1Step 1: Create a memoization array to store results for each node.
2Step 2: For each node, perform a DFS to explore all reachable nodes, marking nodes as visited.
3Step 3: Use memoization to store results for already computed nodes to avoid redundant calculations.

solution.py26 lines

1# Full working Python code
2
3def countVisitedNodes(edges):
4    n = len(edges)
5    result = [-1] * n  # -1 indicates unvisited
6
7    def dfs(node, visited):
8        if result[node] != -1:
9            return result[node]
10        visited.add(node)
11        next_node = edges[node]
12        if next_node in visited:
13            result[node] = len(visited)
14        else:
15            result[node] = dfs(next_node, visited)  # Recur for the next node
16        visited.remove(node)
17        return result[node]
18
19    for i in range(n):
20        if result[i] == -1:
21            dfs(i, set())
22
23    return result
24
25# Example usage
26print(countVisitedNodes([1, 2, 0, 0]))  # Output: [3, 3, 3, 4]

ℹ

Complexity note: The time complexity is O(n) because each node is processed once during the DFS, and memoization prevents redundant calculations. The space complexity is O(n) due to the memoization array and the visited set.

1The graph contains at least one cycle, which is crucial for understanding node visits.
2Using memoization can significantly reduce redundant calculations and improve efficiency.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.