#2876

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Visited Nodes in a Directed Graph

Count Visited Nodes in a Directed Graph uses dynamic programming to solve graph traversal and node visitation counting efficiently.

dynamic programming graph memoization

Problem Statement

You are given a directed graph with n nodes labeled from 0 to n-1 and a list edges where edges[i] indicates an edge from node i to node edges[i]. The task is to determine how many distinct nodes can be visited starting from each node. Specifically, for each node, trace the sequence of nodes that can be visited by following the directed edges and count the number of unique nodes encountered during this process.

Consider the edge case where the graph forms a cycle. What will be the result for each node in that case? The challenge is to compute this count efficiently even for large graphs, leveraging memoization to avoid redundant calculations while ensuring optimal time and space complexity.

Examples

Example 1

Input: edges = [1,2,0,0]

Output: [3,3,3,4]

We perform the process starting from each node in the following way:

Starting from node 0, we visit the nodes 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 3.
Starting from node 1, we visit the nodes 1 -> 2 -> 0 -> 1. The number of different nodes we visit is 3.
Starting from node 2, we visit the nodes 2 -> 0 -> 1 -> 2. The number of different nodes we visit is 3.
Starting from node 3, we visit the nodes 3 -> 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 4.

Example 2

Input: edges = [1,2,3,4,0]

Output: [5,5,5,5,5]

Starting from any node we can visit every node in the graph in the process.

Constraints

n == edges.length
2 <= n <= 105
0 <= edges[i] <= n - 1
edges[i] != i

Solution Approach

State Transition Dynamic Programming

The problem can be efficiently solved by applying dynamic programming with state transitions. For each node, we compute the set of distinct nodes it can visit by recursively following the edges. The result for each node is stored in a memoization table to avoid recomputing results for overlapping subproblems.

Memoization to Avoid Redundant Computations

Memoization ensures that the result for each node is computed only once. Once a node's reachable nodes are calculated, they are stored and reused in subsequent recursive calls, thus significantly improving performance for large graphs.

Graph Traversal with Cycle Detection

The problem involves traversing a directed graph, so detecting cycles is critical. If a node is revisited during traversal, it indicates a cycle. Handling cycles correctly ensures that we count only distinct nodes during each traversal, avoiding infinite loops.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the specific approach taken. In the optimal solution using dynamic programming and memoization, the time complexity is O(n) where n is the number of nodes, as each node is processed once. The space complexity is also O(n) due to the storage requirements for the memoization table.

What Interviewers Usually Probe

The candidate demonstrates a strong understanding of dynamic programming techniques, especially state transitions and memoization.
The candidate recognizes the importance of cycle detection and how to handle it efficiently in graph traversal problems.
The candidate's ability to reduce complexity by avoiding redundant computations shows effective problem-solving skills.

Common Pitfalls or Variants

Common pitfalls

Failing to handle graph cycles correctly, which could lead to infinite loops during traversal.
Not using memoization, resulting in excessive recalculations and poor performance for large inputs.
Overlooking the edge case where every node is part of a cycle, which could lead to incorrect results.

Follow-up variants

Consider a scenario where the graph is a tree instead of a cycle. How would the solution differ?
Modify the problem to allow multiple edges between nodes. How would this affect the solution?
What if the graph has directed edges with weights? How would this impact the dynamic programming approach?

FAQ

What is the main pattern used in Count Visited Nodes in a Directed Graph?

The main pattern in this problem is state transition dynamic programming, which is used to count distinct nodes visited during graph traversal efficiently.

How does memoization help in this problem?

Memoization stores the results of subproblems, preventing redundant calculations and significantly improving performance, especially for large graphs.

What happens if the graph is a cycle?

If the graph forms a cycle, each node can visit all nodes in the cycle, and memoization will ensure that we don't recalculate the same result for each node.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of nodes, due to the use of dynamic programming and memoization to avoid redundant calculations.

How would the solution change for a graph with multiple edges between nodes?

Allowing multiple edges would require modifications to the traversal logic, but memoization would still be helpful to avoid recalculating the result for each node.

terminal

Solution

Solution 1: Basic Tree + Traversal

We can use an array $ans$ to record the answer for each node, and an array $vis$ to record the visit order for each node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)
        ans = [0] * n
        vis = [0] * n
        for i in range(n):
            if not ans[i]:
                cnt, j = 0, i
                while not vis[j]:
                    cnt += 1
                    vis[j] = cnt
                    j = edges[j]
                cycle, total = 0, cnt + ans[j]
                if not ans[j]:
                    cycle = cnt - vis[j] + 1
                    total = cnt
                j = i
                while not ans[j]:
                    ans[j] = max(total, cycle)
                    total -= 1
                    j = edges[j]
        return ans

Continue Practicing

#2328 number of increasing paths in a grid #2858 minimum edge reversals so every node is reachable #1857 largest color value in a directed graph