Count Visited Nodes in a Directed Graph solution and explanation
6 more videos on this problem
2876. Count Visited Nodes in a Directed Graph | Weekly Leetcode 365codingMohan · 19:37 · 3K views
2876. Count Visited Nodes in a Directed Graph (Leetcode Hard)Programming Live with Larry · 30:23 · 844 views
Leetcode Weekly Contest 365 | 100075. Count Visited Nodes in a Directed Graph | PythonBayu Aji · 3:24 · 717 views
【每日一题】LeetCode 2876. Count Visited Nodes in a Directed GraphHuifeng Guan · 14:30 · 403 views
[Eng] Leetcode | Weekly Contest 365 | 2876 Count Visited Nodes in a Directed Graph | C++CyCode · 8:04 · 272 views
100075. Count Visited Nodes in a Directed Graph : LeetCode | C++ | Python | JAVABitByBit - Learn Coding · 0:18 · 125 views
2876. Count Visited Nodes in a Directed GraphJust Coding, with Jie · 20:14 · 117 views
The 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
xand 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.length2 <= n <= 1050 <= edges[i] <= n - 1edges[i] != i
Approach overview
Problem Overview: You are given a directed graph where each node has exactly one outgoing edge. Starting from every node, you keep following edges until a node repeats. The task is to compute how many unique nodes are visited for each starting node.
This structure forms a collection of chains that eventually enter cycles. The key challenge is handling cycles correctly while reusing previously computed results for nodes that lead into those cycles.
Approach 1: DFS with Cycle Detection and Memoization (O(n) time, O(n) space)
Treat the graph as a functional graph (each node has one outgoing edge) and run DFS from each node. Maintain three states for nodes: unvisited, visiting, and processed. When DFS encounters a node already marked as visiting, a cycle is detected. Compute the cycle length and assign that value to all nodes in the cycle. For nodes outside the cycle, propagate results using dp[node] = 1 + dp[next]. Memoization ensures each node is processed once, giving overall O(n) time and O(n) space.
This approach combines graph traversal with dynamic programming. Once a node's result is computed, future DFS calls reuse it instantly. Cycle detection is the critical insight because nodes inside a cycle share the same reachable count.
Approach 2: Iterative Cycle Detection with Path Compression (O(n) time, O(n) space)
An iterative strategy avoids recursion by walking the path from each unprocessed node while storing the traversal order in a stack or list. When the walk reaches a previously visited node, two cases appear: either a cycle is found in the current path or the path merges into a node whose answer is already known.
If a cycle appears, determine its length and assign that value to all nodes inside the cycle. For nodes before the cycle, process the path in reverse order and compute dp[node] = dp[next] + 1. This acts like path compression where each node’s result is finalized exactly once.
The iterative approach is often preferred in languages with recursion limits. It still achieves O(n) time because each node is pushed and processed a constant number of times. The algorithm relies heavily on memoization and careful bookkeeping of node states.
Recommended for interviews: The DFS with cycle detection and memoization approach is usually the most intuitive explanation during interviews. It clearly shows understanding of functional graphs, cycle handling, and dynamic programming reuse. The iterative path-compression variant demonstrates deeper optimization and control over recursion, but both achieve the optimal O(n) complexity expected for this problem.
Approach 1: DFS Approach with Cycle Detection
This approach uses Depth First Search (DFS) to explore each node and detect cycles. Each node keeps track of the nodes visited to count distinct visits. The detection of cycles ensures efficient avoidance of repeated loops.
def count_visited_nodes(edges):
n = len(edges)
visited = [-1] * n
def dfs(node):
stack = []
path_set = set()
while visited[node] == -1:
stack.append(node)
path_set.add(node)
visited[node] = node
node = edges[node]
cycle_size = 0
if node in path_set:
cycle_size = len(stack) - stack.index(node)
for n in stack:
visited[n] = len(stack) if n in path_set else cycle_size
path_set.remove(n)
return visited[stack[0]]
return [dfs(i) for i in range(n)]import java.util.*;
public class Solution {
public int[] countVisitedNodes(int[] edges) {
int n = edges.length;
int[] visited = new int[n];
int[] result = new int[n];
Arrays.fill(visited, -1);
for (int i = 0; i < n; i++) {
if (visited[i] == -1) {
dfs(i, edges, visited, result);
}
}
return result;
}
private void dfs(int node, int[] edges, int[] visited, int[] result) {
List<Integer> stack = new ArrayList<>();
Set<Integer> pathSet = new HashSet<>();
while (visited[node] == -1 && !pathSet.contains(node)) {
stack.add(node);
pathSet.add(node);
visited[node] = node;
node = edges[node];
}
int cycleSize = 0;
if (pathSet.contains(node)) {
cycleSize = stack.size() - stack.indexOf(node);
}
for (int n : stack) {
visited[n] = n != node ? stack.size() : cycleSize;
result[n] = visited[n];
}
}
}#include <vector>
#include <unordered_set>
using namespace std;
void dfs(int node, vector<int>& edges, vector<int>& visited, vector<int>& result) {
vector<int> stack;
unordered_set<int> pathSet;
while (visited[node] == -1 && pathSet.find(node) == pathSet.end()) {
stack.push_back(node);
pathSet.insert(node);
node = edges[node];
}
int cycleSize = 0;
if (pathSet.find(node) != pathSet.end()) {
cycleSize = stack.size() - find(stack.begin(), stack.end(), node) - stack.begin();
}
for (int n : stack) {
visited[n] = n != node ? stack.size() : cycleSize;
result[n] = visited[n];
}
}
vector<int> countVisitedNodes(vector<int>& edges) {
int n = edges.size();
vector<int> visited(n, -1);
vector<int> result(n, 0);
for (int i = 0; i < n; ++i) {
if (visited[i] == -1) {
dfs(i, edges, visited, result);
}
}
return result;
}function countVisitedNodes(edges) {
const n = edges.length;
const visited = Array(n).fill(-1);
const result = Array(n);
function dfs(node) {
const stack = [];
const pathSet = new Set();
while (visited[node] === -1) {
stack.push(node);
pathSet.add(node);
visited[node] = node;
node = edges[node];
}
const cycleSize = pathSet.has(node) ? stack.length - stack.indexOf(node) : 0;
stack.forEach(n => {
visited[n] = pathSet.has(n) ? stack.length : cycleSize;
result[n] = visited[n];
pathSet.delete(n);
});
}
for (let i = 0; i < n; i++) {
if (visited[i] === -1) dfs(i);
}
return result;
}#include <stdio.h>
#include <stdlib.h>
void dfs(int node, int* edges, int* visited, int* result) {
int n = 0, idx = node, cycle_start = -1;
int* stack = (int*)malloc(sizeof(int) * 100000);
while (1) {
if (visited[idx] != -1) {
if (visited[idx] != node) cycle_start = idx;
break;
}
stack[n++] = idx;
visited[idx] = node;
idx = edges[idx];
}
for (int i = 0; i < n; ++i) {
visited[stack[i]] = idx != stack[i] ? n - i : n;
result[stack[i]] = visited[stack[i]];
}
free(stack);
}
int* countVisitedNodes(int* edges, int edgesSize) {
int* visited = (int*)calloc(edgesSize, sizeof(int));
int* result = (int*)malloc(sizeof(int) * edgesSize);
for (int i = 0; i < edgesSize; i++) visited[i] = -1;
for (int i = 0; i < edgesSize; i++) if (visited[i] == -1) dfs(i, edges, visited, result);
free(visited);
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] CountVisitedNodes(int[] edges) {
int n = edges.Length;
int[] visited = new int[n];
int[] result = new int[n];
Array.Fill(visited, -1);
for (int i = 0; i < n; i++) {
if (visited[i] == -1) {
Dfs(i, edges, visited, result);
}
}
return result;
}
private void Dfs(int node, int[] edges, int[] visited, int[] result) {
List<int> stack = new List<int>();
HashSet<int> pathSet = new HashSet<int>();
while (visited[node] == -1 && !pathSet.Contains(node)) {
stack.Add(node);
pathSet.Add(node);
visited[node] = node;
node = edges[node];
}
int cycleSize = 0;
if (pathSet.Contains(node)) {
cycleSize = stack.Count - stack.IndexOf(node);
}
foreach (int n in stack) {
visited[n] = n != node ? stack.Count : cycleSize;
result[n] = visited[n];
}
}
}We track visited nodes using a list where the index represents each node and its value represents whether the node was visited during this process. The method leverages a DFS pattern where each node's path is traversed, recording the path in a stack and leveraging a set for cycle detection.
Time complexity: O(n) where n is the number of nodes as each node is visited at most once.
Space complexity: O(n) for auxiliary data structures.
Approach 2: Iterative Cycle Detection and Path Compression
This approach implements an iterative approach to detect cycles and uses path compression techniques to consolidate previous results for repeated nodes. It arrays thorough edge exploration, directly adjusting visited node counts efficiently.
def count_visited_nodes(edges):
n = len(edges)
res = [0] * n
visited = [False] * n
def visit(v):
count = 0
p = v
stack = []
while not visited[p]:
stack.append(p)
visited[p] = True
p = edges[p]
count += 1
if p in stack:
cycle_length = count - stack.index(p)
while stack:
node = stack.pop()
res[node] = cycle_length if node in stack else count
else:
while stack:
node = stack.pop()
res[node] = count
for i in range(n):
if not visited[i]:
visit(i)
return resimport java.util.*;
public class Solution {
public int[] countVisitedNodes(int[] edges) {
int n = edges.length;
int[] result = new int[n];
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
visit(edges, result, visited, i);
}
}
return result;
}
private void visit(int[] edges, int[] result, boolean[] visited, int start) {
int count = 0;
Stack<Integer> stack = new Stack<>();
int node = start;
while (!visited[node]) {
stack.add(node);
visited[node] = true;
node = edges[node];
count++;
}
int cycleLength = count;
while (!stack.isEmpty()) {
int n = stack.pop();
result[n] = n == node ? cycleLength : count;
cycleLength--;
}
}
}#include <vector>
using namespace std;
void visit(vector<int>& edges, vector<int>& res, vector<bool>& visited, int start) {
int count = 0;
vector<int> stack;
int p = start;
while (!visited[p]) {
stack.push_back(p);
visited[p] = true;
p = edges[p];
count++;
}
int cycleLength = count;
while (!stack.empty()) {
int node = stack.back();
stack.pop_back();
cycleLength -= node == p;
res[node] = cycleLength > 0 ? cycleLength : count;
}
}
vector<int> countVisitedNodes(vector<int>& edges) {
int n = edges.size();
vector<int> res(n, 0);
vector<bool> visited(n, false);
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
visit(edges, res, visited, i);
}
}
return res;
}function countVisitedNodes(edges) {
const n = edges.length;
const visited = Array(n).fill(false);
const result = Array(n);
function visit(node) {
const stack = [];
let count = 0;
while (!visited[node]) {
stack.push(node);
visited[node] = true;
node = edges[node];
count++;
}
const cycleLength = count;
while (stack.length) {
const n = stack.pop();
result[n] = cycleLength;
}
}
for (let i = 0; i < n; i++) {
if (!visited[i]) visit(i);
}
return result;
}#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
void visit(int* edges, int* res, bool* visited, int start) {
int count = 0;
int stack[100000];
int p = start;
while (!visited[p]) {
stack[count++] = p;
visited[p] = true;
p = edges[p];
}
int cycleLength = 0;
for (int i = 0; i < count; ++i) {
if (stack[i] == p) {
cycleLength = count - i;
break;
}
}
for (int i = 0; i < count; ++i) {
res[stack[i]] = i < cycleLength ? cycleLength : count;
}
}
int* countVisitedNodes(int* edges, int edgesSize) {
bool visited[edgesSize];
int* res = (int*) malloc(edgesSize * sizeof(int));
for (int i = 0; i < edgesSize; ++i) visited[i] = false;
for (int i = 0; i < edgesSize; ++i) {
if (!visited[i]) {
visit(edges, res, visited, i);
}
}
return res;
}using System;
public class Solution {
public int[] CountVisitedNodes(int[] edges) {
int n = edges.Length;
int[] result = new int[n];
bool[] visited = new bool[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Visit(edges, result, visited, i);
}
}
return result;
}
private void Visit(int[] edges, int[] result, bool[] visited, int start) {
int count = 0;
System.Collections.Generic.Stack<int> stack = new System.Collections.Generic.Stack<int>();
int node = start;
while (!visited[node]) {
stack.Push(node);
visited[node] = true;
node = edges[node];
count++;
}
while (stack.Count > 0) {
int n = stack.Pop();
result[n] = --count;
}
}
}This Python code iteratively traverses through each node, marking nodes along the path as visited. If a node previously visits within the same path, counting signals a cycle start. Else collected path-length is assigned to non-repeating nodes.
Time complexity: O(n).
Space complexity: O(n).
Approach 3: Basic Tree + Traversal
We can use an array ans to record the answer for each node, and an array vis to record the visit order for each node.
For each node i, if it has not been visited yet, we start traversing from node i. There are two cases:
- If we encounter a node that has been visited before during the traversal, then we must have first entered the cycle and then walked around the cycle. For nodes outside the cycle, their answer is the length of the cycle plus the distance from the node to the cycle; for nodes inside the cycle, their answer is the length of the cycle.
- If we encounter a node that has been visited before during the traversal, then for each visited node, its answer is the distance from the current node to this node plus the answer of this node.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array edges.
function countVisitedNodes(edges: number[]): number[] {
const n = edges.length;
const ans: number[] = Array(n).fill(0);
const vis: number[] = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
if (ans[i] === 0) {
let [cnt, j] = [0, i];
while (vis[j] === 0) {
vis[j] = ++cnt;
j = edges[j];
}
let [cycle, total] = [0, 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[j];
}
}
}
return ans;
}func countVisitedNodes(edges []int) []int {
n := len(edges)
ans := make([]int, n)
vis := make([]int, n)
for i := range ans {
if ans[i] == 0 {
cnt, j := 0, i
for vis[j] == 0 {
cnt++
vis[j] = cnt
j = edges[j]
}
cycle, total := 0, cnt+ans[j]
if ans[j] == 0 {
cycle = cnt - vis[j] + 1
}
j = i
for ans[j] == 0 {
ans[j] = max(total, cycle)
total--
j = edges[j]
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS Approach with Cycle Detection | Time complexity: O(n) where n is the number of nodes as each node is visited at most once. |
| Iterative Cycle Detection and Path Compression | Time complexity: O(n). |
| Basic Tree + Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Cycle Detection and Memoization | O(n) | O(n) | Most common interview approach; clear recursion and DP reuse |
| Iterative Cycle Detection with Path Compression | O(n) | O(n) | Avoid recursion limits and process paths iteratively |
Frequently asked questions
Is Count Visited Nodes in a Directed Graph easy or hard?
Count Visited Nodes in a Directed Graph is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the functional graph structure and correctly handling cycles while propagating results to nodes leading into those cycles.
How to solve Count Visited Nodes in a Directed Graph in O(n)?
Model the graph as a functional graph where every node has exactly one outgoing edge. Run DFS or iterative traversal while tracking node states to detect cycles. Once a cycle is found, assign its size to cycle nodes and propagate counts outward using dp[node] = 1 + dp[next]. Memoization guarantees each node's result is computed only once.
Count Visited Nodes in a Directed Graph Python or Java solution?
Python and Java implementations usually follow the same logic: maintain a visited state array, perform DFS to detect cycles, compute cycle sizes, and store results in a dp array. Both languages achieve O(n) time and O(n) space when memoization is applied.
What is the best approach for Count Visited Nodes in a Directed Graph?
The optimal approach uses DFS with cycle detection combined with dynamic programming memoization. Detect cycles in the functional graph, assign the cycle length to all nodes in the cycle, and propagate results backward for nodes leading into the cycle. This ensures each node is processed once, resulting in O(n) time and O(n) space complexity.
What data structure is used in Count Visited Nodes in a Directed Graph?
The solution primarily uses arrays or lists to represent the outgoing edge mapping, along with auxiliary arrays for node states and dynamic programming results. A stack or recursion stack helps track the current path during cycle detection.
What is the time complexity of Count Visited Nodes in a Directed Graph?
The optimal solution runs in O(n) time because each node is visited and resolved once. Cycle detection and memoization prevent repeated traversals of the same paths. Space complexity is O(n) due to recursion stacks or auxiliary arrays used for state tracking and DP storage.
Is Count Visited Nodes in a Directed Graph asked at Google or other top companies?
Problems involving functional graphs, cycle detection, and dynamic programming appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require detecting cycles and computing path lengths in directed graphs are common in senior-level algorithm rounds.