Count Visited Nodes in a Directed Graph

HARD

Description

There is a directed graph consisting of n nodes numbered from 0 to n - 1 and n directed edges.

You are given a 0-indexed array edges where edges[i] indicates that there is an edge from node i to node edges[i].

Consider the following process on the graph:

You start from a node x and keep visiting other nodes through edges until you reach a node that you have already visited before on this same process.

Return an array answer where answer[i] is the number of different nodes that you will visit if you perform the process starting from node i.

Example 1:

Input: edges = [1,2,0,0]
Output: [3,3,3,4]
Explanation: 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]
Explanation: Starting from any node we can visit every node in the graph in the process.

Constraints:

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

Approaches

Checkout 2 different approaches to solve Count Visited Nodes in a Directed Graph. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

This approach directly simulates the process described in the problem for each starting node. For every node from 0 to n-1, we traverse the graph, keeping track of the nodes visited in the current path using a HashSet. The traversal stops when we encounter a node that has already been seen in this specific traversal. The number of nodes collected in the HashSet gives us the answer for the starting node.

Algorithm

Create an integer array answer of size n.
For each node i from 0 to n-1:
- Create a HashSet<Integer> pathVisited to keep track of nodes visited in the current traversal.
- Initialize currentNode = i.
- In a loop, continue as long as currentNode can be added to pathVisited (meaning it's a new node for this path).
  - In each iteration, update currentNode to edges[currentNode].
- The size of pathVisited is the number of unique nodes visited. Store this in answer[i].
Return the answer array.

We initialize an answer array of size n. We then iterate through each node i from 0 to n-1 to calculate answer[i]. For each i, we begin a simulation. A HashSet called visited_in_path is used to store nodes visited in the current traversal, which starts from node i. We also use a counter, count, initialized to 0. We start with currentNode = i. In a loop, as long as currentNode is not in visited_in_path, we add it to the set, increment our count, and move to the next node by setting currentNode = edges[currentNode]. When the loop terminates, it means we've encountered a node that was already in visited_in_path. The final value of count (or the size of the set) is the number of different nodes visited, which we store in answer[i]. After iterating through all possible starting nodes, the answer array is complete and returned.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] countVisitedNodes(int[] edges) {
        int n = edges.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            Set<Integer> visitedInPath = new HashSet<>();
            int currentNode = i;
            while (visitedInPath.add(currentNode)) {
                currentNode = edges[currentNode];
            }
            answer[i] = visitedInPath.size();
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n^2) - For each of the `n` starting nodes, the traversal can take up to O(n) steps in the worst case (a single long path). This results in a quadratic time complexity.Space Complexity: O(n) - In each simulation, the `HashSet` can store up to `n` nodes in the worst-case scenario where the path traverses all nodes before repeating.

Pros and Cons

Pros:

Simple to understand and implement.
Directly follows the logic described in the problem statement.

Cons:

Highly inefficient due to redundant computations. The traversal from one node might largely overlap with the traversal from another, but this work is repeated.
The time complexity is too high for the given constraints, which will likely result in a 'Time Limit Exceeded' error on most platforms.

Code Solutions

Checking out 3 solutions in different languages for Count Visited Nodes in a Directed Graph. Click on different languages to view the code.

class Solution { public int [] countVisitedNodes ( List < Integer > edges ) { int n = edges . size (); int [] ans = new int [ n ]; int [] vis = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { if ( ans [ i ] == 0 ) { int cnt = 0 , j = i ; while ( vis [ j ] == 0 ) { vis [ j ] = ++ cnt ; j = edges . get ( j ); } int cycle = 0 , total = cnt + ans [ j ]; if ( ans [ j ] == 0 ) { cycle = cnt - vis [ j ] + 1 ; } j = i ; while ( ans [ j ] == 0 ) { ans [ j ] = Math . max ( total --, cycle ); j = edges . get ( j ); } } } return ans ; } }

Video Solution

Watch the video walkthrough for Count Visited Nodes in a Directed Graph

Patterns:

Dynamic ProgrammingMemoization

Data Structures:

Graph

Companies:

BNY Mellon |