2876. Count Visited Nodes in a Directed Graph LeetCode Solution
In this guide, you will get 2876. Count Visited Nodes in a Directed Graph LeetCode Solution with the best time and space complexity. The solution to Count Visited Nodes in a Directed Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Visited Nodes in a Directed Graph
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.
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 <= 105
0 <= edges[i] <= n – 1
edges[i] != i
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2876. Count Visited Nodes in a Directed Graph LeetCode Solution in C++
class Solution {
public:
vector<int> countVisitedNodes(vector<int>& edges) {
const int n = edges.size();
vector<int> ans(n);
vector<int> inDegrees(n);
vector<bool> seen(n);
queue<int> q;
stack<int> stack;
for (const int v : edges)
++inDegrees[v];
// Perform topological sorting.
for (int i = 0; i < n; ++i)
if (inDegrees[i] == 0)
q.push(i);
// Push non-cyclic nodes to stack.
while (!q.empty()) {
const int u = q.front();
q.pop();
if (--inDegrees[edges[u]] == 0)
q.push(edges[u]);
stack.push(u);
seen[u] = true;
}
// Fill the length of cyclic nodes.
for (int i = 0; i < n; ++i)
if (!seen[i])
fillCycle(edges, i, seen, ans);
// Fill the length of non-cyclic nodes.
while (!stack.empty()) {
const int u = stack.top();
stack.pop();
ans[u] = ans[edges[u]] + 1;
}
return ans;
}
private:
void fillCycle(const vector<int>& edges, int start, vector<bool>& seen,
vector<int>& ans) {
int cycleLength = 0;
for (int u = start; !seen[u]; u = edges[u]) {
++cycleLength;
seen[u] = true;
}
ans[start] = cycleLength;
for (int u = edges[start]; u != start; u = edges[u])
ans[u] = cycleLength;
}
}; /* code provided by PROGIEZ */
2876. Count Visited Nodes in a Directed Graph LeetCode Solution in Java
class Solution {
public int[] countVisitedNodes(List<Integer> edges) {
final int n = edges.size();
int[] ans = new int[n];
int[] inDegrees = new int[n];
boolean[] seen = new boolean[n];
Queue<Integer> q = new ArrayDeque<>();
Stack<Integer> stack = new Stack<>();
for (int v : edges)
++inDegrees[v];
// Perform topological sorting.
for (int i = 0; i < n; ++i)
if (inDegrees[i] == 0)
q.add(i);
// Push non-cyclic nodes to stack.
while (!q.isEmpty()) {
final int u = q.poll();
if (--inDegrees[edges.get(u)] == 0)
q.add(edges.get(u));
stack.push(u);
seen[u] = true;
}
// Fill the length of cyclic nodes.
for (int i = 0; i < n; ++i)
if (!seen[i])
fillCycle(edges, i, seen, ans);
// Fill the length of non-cyclic nodes.
while (!stack.isEmpty()) {
final int u = stack.pop();
ans[u] = ans[edges.get(u)] + 1;
}
return ans;
}
private void fillCycle(List<Integer> edges, int start, boolean[] seen, int[] ans) {
int cycleLength = 0;
for (int u = start; !seen[u]; u = edges.get(u)) {
++cycleLength;
seen[u] = true;
}
ans[start] = cycleLength;
for (int u = edges.get(start); u != start; u = edges.get(u))
ans[u] = cycleLength;
}
} // code provided by PROGIEZ
2876. Count Visited Nodes in a Directed Graph LeetCode Solution in Python
class Solution:
def countVisitedNodes(self, edges: list[int]) -> list[int]:
n = len(edges)
ans = [0] * n
inDegrees = [0] * n
seen = [False] * n
stack = []
for v in edges:
inDegrees[v] += 1
# Perform topological sorting.
q = collections.deque([i for i, d in enumerate(inDegrees) if d == 0])
# Push non-cyclic nodes to stack.
while q:
u = q.popleft()
inDegrees[edges[u]] -= 1
if inDegrees[edges[u]] == 0:
q.append(edges[u])
stack.append(u)
seen[u] = True
# Fill the length of cyclic nodes.
for i in range(n):
if not seen[i]:
self._fillCycle(edges, i, seen, ans)
# Fill the length of non-cyclic nodes.
while stack:
u = stack.pop()
ans[u] = ans[edges[u]] + 1
return ans
def _fillCycle(
self,
edges: list[int],
start: int,
seen: list[bool],
ans: list[int],
) -> None:
cycleLength = 0
u = start
while not seen[u]:
cycleLength += 1
seen[u] = True
u = edges[u]
ans[start] = cycleLength
u = edges[start]
while u != start:
ans[u] = cycleLength
u = edges[u] # code by PROGIEZ
