We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Visited Nodes in a Directed Graph

Number: 3140

Difficulty: Hard

Paid? No

Companies: Amazon, BNY Mellon

Problem Description

Given a directed graph represented by an array "edges" of size n, where each node i has an edge to edges[i], determine for every starting node the number of unique nodes visited before a node is revisited (i.e. when a cycle is encountered). In other words, simulate a process that follows the edges starting at each node until a previously seen node in that same process reoccurs, and report the count of distinct nodes visited.

Key Insights

  • The graph is a functional graph where each node has exactly one outgoing edge.
  • The structure is composed of cycles with trees feeding into them.
  • When performing the process from any starting node, you eventually enter a cycle.
  • Memoization can be used to store the answer for nodes that have been computed to avoid recomputation.
  • Detect cycles by keeping track of the order of nodes encountered in the current processing chain.

Space and Time Complexity

Time Complexity: O(n) – Each node is processed at most once. Space Complexity: O(n) – Additional storage is used for memoization and tracking the current DFS/iteration chain.

Solution

The key is to notice that this is a functional graph where each node has exactly one outgoing edge. For each starting node, we simulate the process by following the chain of directed edges. We maintain a list (or stack) to record the order of nodes visited during the current exploration. A dictionary (or similar structure) maps each node to its index in the current chain; if we encounter a node already in this dictionary, a cycle is detected. The cycle length and the nodes leading into it can then be used to assign answers:

  1. Nodes in the cycle get a count equal to the length of the cycle.
  2. Nodes leading into the cycle get a count that is the distance from that node to the start of the cycle plus the cycle length.
  3. If we reach a node whose answer is already computed (memoized), we can use that to quickly calculate the result for the chain. This approach ensures that each node is visited at most once, achieving linear time complexity.

Code Solutions

# Python solution with line-by-line comments

def countVisitedNodes(edges):
    n = len(edges) 
    # Initialize result array with -1 indicating not computed yet.
    result = [-1] * n
    
    # Define a helper function to perform the DFS/chain exploration
    def dfs(start):
        # Use a dictionary to keep track of the current chain and its index.
        index_map = {}
        path = []  # record the nodes in the current exploration
        
        current = start
        while True:
            # If the result for the current node is already computed, use it.
            if result[current] != -1:
                # Propagate the answer for nodes in 'path'
                accrued = result[current]
                for i in range(len(path)-1, -1, -1):
                    accrued += 1
                    result[path[i]] = accrued
                return
            
            # If we detect a cycle (current node already in our chain):
            if current in index_map:
                # Cycle detected; compute cycle length.
                cycle_start_index = index_map[current]
                cycle_length = len(path) - cycle_start_index
                # Assign cycle length to all nodes in the cycle.
                for i in range(cycle_start_index, len(path)):
                    result[path[i]] = cycle_length
                # For nodes before the cycle, assign result as (distance to cycle + cycle_length)
                for i in range(cycle_start_index-1, -1, -1):
                    result[path[i]] = result[path[i+1]] + 1
                return
            
            # Mark this node in the current chain.
            index_map[current] = len(path)
            path.append(current)
            # Move to the next node following the directed edge.
            current = edges[current]
    
    # Process each node that hasn't been computed yet.
    for i in range(n):
        if result[i] == -1:
            dfs(i)
    return result

# Example usage:
# print(countVisitedNodes([1,2,0,0]))
← Back to All Questions