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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Visited Nodes in a Directed Graph

Difficulty: Hard

Problem Description

You are given a directed graph consisting of n nodes numbered from 0 to n - 1 and n directed edges represented by an array edges where edges[i] indicates an edge from node i to edges[i]. Starting from each node, you need to determine how many different nodes can be visited before encountering a cycle. Return an array where answer[i] is the number of different nodes visited starting from node i.

Key Insights

  • The graph contains cycles due to the directed edges.
  • Starting from any node, the traversal can lead to a cycle, so we need to track visited nodes.
  • We can use Depth-First Search (DFS) or memoization to efficiently explore the nodes.
  • The challenge lies in efficiently handling the potentially large number of nodes (up to 100,000).

Space and Time Complexity

Time Complexity: O(n) - Each node is visited once during the traversal. Space Complexity: O(n) - For the recursion stack in DFS and to store visited states.

Solution

We can solve this problem using Depth-First Search (DFS) combined with memoization to avoid redundant calculations. The main steps include:

  1. Initialize an answer array to store the number of unique nodes visited from each starting node.
  2. Use a DFS function that tracks the current node and the nodes visited during the traversal.
  3. If a node is revisited, we can determine the cycle length and all nodes visited in that cycle.
  4. Store the results in the answer array for each node.

This approach ensures we efficiently count the unique nodes visited without redundant checks.

Code Solutions

def countVisitedNodes(edges):
    n = len(edges)
    answer = [-1] * n  # To store the result for each node
    visited = [False] * n  # To track visited nodes

    def dfs(node, visited_set):
        # If we reach a node that was already visited in the current path
        if answer[node] != -1:
            return answer[node]
        
        if node in visited_set:
            return len(visited_set)  # Cycle detected, return the size of the visited set
        
        visited_set.add(node)  # Add current node to the path
        next_node = edges[node]
        result = dfs(next_node, visited_set)  # Go to the next node
        
        visited_set.remove(node)  # Backtrack
        answer[node] = result  # Store the result for the current node
        return result

    for i in range(n):
        if answer[i] == -1:
            dfs(i, set())  # Start DFS from each unvisited node
    
    return answer
← Back to All Questions