Problem Description

In this problem, we are given a directed graph which is represented by a 0-indexed array edges. Each element edges[i] indicates that there is a directed edge from node i to node edges[i]. The graph consists of n nodes labeled from 0 to n - 1, and n directed edges.

The task is to determine, for each starting node i, how many distinct nodes can be visited if we follow the directed edges starting from node i until we return to any node visited earlier in the same process. This essentially means we're calculating how many unique nodes we encounter before we enter a cycle or revisit any node during traversal which implies the start of a cycle.

Intuition

To solve this problem, we need to keep track of two key pieces of information:

• The number of nodes visited in the current traversal, starting from each node i.
• Whether or not we've entered a cycle, and if so, the length of that cycle.

To do this, we can start at each unvisited node and follow edges to traverse the graph, using an array vis to record the order in which we visited nodes. During the traversal, we do one of two things:

• If we find a node that has already been visited in this traversal (vis[j] is nonzero), we then know that we have entered a cycle. We now know the number of nodes outside the cycle that have been visited and also the length of the cycle. For each unvisited node, its answer is then the number of unique nodes visited — which is the sum of the length of the cycle and the path length to the cycle for nodes outside the cycle, or simply the cycle length for nodes inside the cycle.

• If we find a node for which we've already computed an answer, then, for each visited node, its answer is the distance from the current node to this node plus the answer of this node we've already computed.

The algorithm involves iterating over each of the nodes of the graph and performing a depth-first traversal. During the traversal, we update the vis array to reflect the visitation order and calculate the necessary counts for the cycle and the path leading to the cycle. Once a traversal from a starting node is completed or we encounter a previously computed answer, we backtrack while updating the ans array with the number of nodes that can be visited for each start node.

This method allows us to efficiently compute the number of nodes that can be visited from each starting node by leveraging the information gained during each traversal and avoiding redundant computations.

Learn more about Graph, Memoization and Dynamic Programming patterns.

Solution Approach

The solution implements a form of depth-first traversal. Here's a breakdown of the approach based on the provided Reference Solution Approach and Python solution:

1. Initialization: Create two arrays, ans and vis. ans will store the final answer for each node (i.e., the number of different nodes visited), and vis will store the visitation order for each node. Both are initially filled with zeros.

2. Outer Loop: Iterate through all the nodes with a for loop, using each node as a starting point for the process.

3. Traversal Initiation: For each starting node, if ans[i] is zero, meaning that we have not computed the answer for this node, we start traversing from this node i.

4. Inner Loop - Traversing Nodes: In a while loop, continue to follow the directed edges until we encounter a node that we have already visited in this traversal (which implies a cycle) or a node that we have already computed the answer for in a different traversal. For each node j we visit:

   • Increment the count (cnt) which keeps track of how many nodes we have visited in this traversal.
   • Update vis[j] with the visitation order cnt.
   • Move to the next node using j = edges[j].

5. Cycle and Path Detection: Once we've either hit an already visited node within this traversal or an already computed node, calculate the cycle length if necessary and the total number of nodes visited. If a cycle is detected, the length is determined by the difference between the current cnt value and the visitation order of the node that's part of the cycle (vis[j]).

6. Backtracking and Answer Update: Once we've hit a node for which an answer was already computed or the start of a cycle has been determined, loop back through the nodes we just visited to update their answers (ans[j]). The nodes inside the cycle all have the same answer (the cycle length).

7. Population of Answers: Loop through the previously visited nodes and update their answers based on whether they are inside or outside the cycle.

The implementation uses the max(total, cycle) to ensure the answer for each node is either the total number of nodes visited (for those outside the cycle) or the length of the cycle (for those inside the cycle).

Data Structures Used:

• One-dimensional lists (ans to store answers for each node, vis to store visitation order).

Algorithm Patterns Used:

• Depth-First Search (DFS) traversal to explore the graph.
• Cycle detection and cycle length calculation within a directed graph.
• Backtracking to propagate the calculated answers to all starting points included in a traversal.

This approach minimizes redundant computations and efficiently calculates the answers for all the nodes in a directed graph that potentially contains cycles.

Example Walkthrough

Let's illustrate the solution approach using a small example with a directed graph:

Suppose we have the following directed graph represented by edges = [1, 2, 0, 4, 5, 3].

This means we have six nodes, and the directed edges are as follows:

• Edge from node 0 to node 1
• Edge from node 1 to node 2
• Edge from node 2 to node 0 (forming a cycle with nodes 0, 1, 2)
• Edge from node 3 to node 4
• Edge from node 4 to node 5
• Edge from node 5 to node 3 (forming a cycle with nodes 3, 4, 5)

We can visualize the graph like this:

  0 → 1 → 2
  ↑    ↓
  └────┘

  3 → 4 → 5
  ↑       ↓
  └───────┘

Now, let's walk through the solution steps:

1. Initialization: Create two arrays ans and vis with length 6 (the number of nodes), initializing all values to zero.

2. Outer Loop: We start with node 0 and since ans[0] is zero, we begin traversal.

3. Traversal Initiation: Set cnt = 1 since we are starting traversal from node 0. Then we set vis[0] = 1 to indicate node 0 is visited first.

4. Inner Loop - Traversing Nodes: We follow the directed edge to node 1. Increase cnt to 2 and mark vis[1] = 2. Next, visit node 2, increment cnt to 3, and mark vis[2] = 3.

5. Cycle Detection: When we attempt to move from node 2 to node 0, we notice that vis[0] is already marked (indicating a cycle since we've returned to an already visited node within this traversal). The cycle includes nodes 0, 1, and 2.

6. Backtracking and Answer Update: The length of the cycle is cnt - vis[0] = 3 - 1 = 2. We then backtrack, updating ans[0], ans[1], and ans[2] to 2 as they are part of the cycle.

7. Population of Answers for Nodes Outside the Cycle: Since there are no nodes outside the cycle for this starting node, we don't update any additional answers.

Next, we would proceed with node 3 as the starting node and repeat the steps. Eventually, we would identify the cycle among nodes 3, 4, and 5, and after backtracking and updating, we'd have ans[3], ans[4], and ans[5] all set to 3.

After processing all nodes, the final ans array is [2, 2, 2, 3, 3, 3], indicating the number of nodes we can visit from each starting node before encountering a cycle or revisiting a node.

During the entire process, we only traverse the graph starting from each node one time, ensuring an efficient solution that avoids redundant calculations. The vis array helps to quickly determine the presence of a cycle and the nodes involved in the cycle for accurate answer updates.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(n). This is because each node is visited exactly once in a single pass to count the number of nodes visited before reaching a previously visited node (or itself, forming a cycle). The outer loop runs for each node (n iterations), and the inner while loops process each node only once, without revisits due to the vis array marking visited nodes.

The space complexity of the given code is also O(n). This is due to the allocation of two arrays of size n: ans array to store the answer for each node, and the vis array to keep track of the visitation status of each node. There are no additional data structures or recursive calls that would increase the space usage, so it remains linear with respect to the number of nodes n.

Learn more about how to find time and space complexity quickly using problem constraints.