Count Visited Nodes in a Directed Graph — LeetCode 2876 Python Solution

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].

Example

Input

edges = [1,2,0,0]

Output

[3,3,3,4]

Explanation

We perform the process starting from each node in the following way:

Python solution

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)
        ans = [0] * n
        vis = [0] * n
        for i in range(n):
            if not ans[i]:
                cnt, j = 0, i
                while not vis[j]:
                    cnt += 1
                    vis[j] = cnt
                    j = edges[j]
                cycle, total = 0, cnt + ans[j]
                if not ans[j]:
                    cycle = cnt - vis[j] + 1
                    total = cnt
                j = i
                while not ans[j]:
                    ans[j] = max(total, cycle)
                    total -= 1
                    j = edges[j]
        return ans

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2876. Count Visited Nodes in a Directed Graph is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems