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:
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.
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] != iThis 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.
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.
C
Java
C++
C#
JavaScript
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.
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.
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.
C
Java
C++
C#
JavaScript
Time complexity: O(n).
Space complexity: O(n).
| 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). |
Google Graph Interview Question! | Leetcode 200 - Number of Islands • Greg Hogg • 50,854 views views
Watch 9 more video solutions →Practice Count Visited Nodes in a Directed Graph with our built-in code editor and test cases.
Practice on FleetCode