Count Visited Nodes in a Directed Graph - Practice Coding Problems

Count Visited Nodes in a Directed Graph - Problem

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.

Input & Output

Example 1 — Basic Cycle

$ Input: edges = [2,0,3,2]

› Output: [2,3,2,3]

💡 Note: Starting from node 0: 0→2→0 (visits 2 nodes). Starting from node 1: 1→0→2→0 (visits 3 nodes). Starting from node 2: 2→0→2 (visits 2 nodes). Starting from node 3: 3→2→0→2 (visits 3 nodes).

Example 2 — Self Loop

$ Input: edges = [1,2,2,4,4]

› Output: [3,3,1,2,1]

💡 Note: Node 0: 0→1→2→2 (visits 3 nodes, stops at self-loop). Node 1: 1→2→2 (visits 2 nodes). Node 2: 2→2 (visits 1 node, immediate self-loop). Node 3: 3→4→4 (visits 2 nodes). Node 4: 4→4 (visits 1 node).

Example 3 — Linear Chain

$ Input: edges = [1,2,0]

› Output: [3,3,3]

💡 Note: All nodes eventually cycle through 0→1→2→0, so each starting point visits all 3 nodes before repeating.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed graph where each node points to exactly one other node

Walk Process

Follow edges until revisiting a node

Count Nodes

Return number of unique nodes visited from each start

Key Takeaway

🎯 Key Insight: Every path eventually hits a cycle - we can optimize by detecting cycles and reusing results

Asked in

G Google 28 M Microsoft 15 A Amazon 12 f Meta 8

The key insight is that every path in a functional graph eventually leads to a cycle. We can use cycle detection with memoization to efficiently count visited nodes. The optimal approach uses DFS with node coloring (WHITE/GRAY/BLACK) to detect cycles and calculate results in O(n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Memoization	O(n)	O(n)	Use DFS to explore paths and cache results to avoid recomputation
Cycle Detection with Path Tracking	O(n)	O(n)	Efficiently detect cycles and calculate visited counts in a single pass
Brute Force Simulation	O(n²)	O(n)	Simulate the walk from each starting node independently

DFS with Memoization — Algorithm Steps

Use DFS to explore from each unprocessed node
Track path during exploration to detect cycles
Once a cycle is found, calculate visited count for all nodes in path
Cache results to avoid recomputation

Visualization

Tap to expand

Step-by-Step Walkthrough

Explore Path

Use DFS to explore path and detect cycles

Cache Results

Store results for processed nodes

Reuse Cache

Use cached values for subsequent queries

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int memo[100000];
bool memoSet[100000];
int* edges;

int dfs(int node, int* path, int pathLen, bool* pathSet) {
    if (memoSet[node]) {
        return memo[node];
    }
    
    if (pathSet[node]) {
        int cycleStartIdx = -1;
        for (int i = 0; i < pathLen; i++) {
            if (path[i] == node) {
                cycleStartIdx = i;
                break;
            }
        }
        
        int cycleNodes = pathLen - cycleStartIdx;
        
        for (int i = cycleStartIdx; i < pathLen; i++) {
            memo[path[i]] = cycleNodes;
            memoSet[path[i]] = true;
        }
        
        return cycleNodes;
    }
    
    path[pathLen] = node;
    pathSet[node] = true;
    
    int nextNode = edges[node];
    int result = 1 + dfs(nextNode, path, pathLen + 1, pathSet);
    
    pathSet[node] = false;
    memo[node] = result;
    memoSet[node] = true;
    
    return result;
}

int* solution(int* edgesArray, int edgesSize, int* returnSize) {
    edges = edgesArray;
    *returnSize = edgesSize;
    
    memset(memoSet, false, sizeof(memoSet));
    
    int* answer = (int*)malloc(edgesSize * sizeof(int));
    int path[100000];
    bool pathSet[100000];
    
    for (int i = 0; i < edgesSize; i++) {
        if (!memoSet[i]) {
            memset(pathSet, false, sizeof(pathSet));
            dfs(i, path, 0, pathSet);
        }
        answer[i] = memo[i];
    }
    
    return answer;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int edges[1000];
    int size = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    
    while (token != NULL) {
        edges[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(edges, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each node is visited at most twice - once during exploration and once when result is cached

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth plus memoization cache and path tracking

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler