Count Visited Nodes in a Directed Graph

Count Visited Nodes in a Directed Graph

What is this problem about?

The Count Visited Nodes in a Directed Graph interview question asks you to find the number of unique nodes reachable from each node in a graph where every node has exactly one outgoing edge. In such a graph, also known as a functional graph, the path starting from any node eventually enters a cycle. You need to return an array where each entry represents the total number of distinct nodes visited if you start a traversal from that specific node.

Why is this asked in interviews?

Companies like Google and Amazon use the Count Visited Nodes in a Directed Graph coding problem to evaluate a candidate's mastery of graph cycles and optimization techniques. Since the graph can have up to $10^5$ nodes, a naive traversal from each node would result in O(n^2) complexity, which is too slow. It tests your ability to use Memoization and identify the unique properties of functional graphs to achieve an O(n) solution.

Algorithmic pattern used

This problem follows a Graph and Dynamic Programming pattern. The key is to identify the cycles within the graph.

1. Cycle Detection: Use a traversal (like DFS) to identify nodes that form a cycle.
2. Cycle Size Calculation: All nodes in a cycle have the same "visited nodes" count, which is equal to the cycle's length.
3. Memoization for Paths: For nodes not in a cycle, the count is $1 + ext{count of its neighbor}$. By processing nodes in reverse topological order (or using recursion with memoization), you can calculate the result efficiently.

Example explanation

Imagine a graph with nodes 0 to 4:

• 0 -> 1
• 1 -> 2
• 2 -> 0 (Cycle: 0, 1, 2)
• 3 -> 0
• 4 -> 3 For nodes 0, 1, and 2, they are in a cycle of length 3. So res[0]=3, res[1]=3, res[2]=3. Starting from 3, you visit 3, then 0, 1, 2. Total unique nodes = 4. res[3] = 1 + res[0] = 4. Starting from 4, you visit 4, 3, 0, 1, 2. Total unique nodes = 5. res[4] = 1 + res[3] = 5.

Common mistakes candidates make

• Re-traversing Cycles: Failing to cache the results for nodes already identified as part of a cycle, leading to redundant work.
• Recursion Limit: Forgetting that a deep graph path can cause a stack overflow in languages like Python. Iterative DFS or increasing the recursion limit is necessary.
• Miscounting cycle nodes: Not correctly identifying the entry point of a cycle during DFS.

Interview preparation tip

Functional graphs always consist of a set of components, where each component has exactly one cycle. Recognizing this structure immediately simplifies many directed graph problems.