<p>There is a <strong>directed</strong> graph consisting of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code> and <code>n</code> directed edges.</p>

<p>You are given a <strong>0-indexed</strong> array <code>edges</code> where <code>edges[i]</code> indicates that there is an edge from node <code>i</code> to node <code>edges[i]</code>.</p>

<p>Consider the following process on the graph:</p>

<ul>
	<li>You start from a node <code>x</code> and keep visiting other nodes through edges until you reach a node that you have already visited before on this <strong>same</strong> process.</li>
</ul>

<p>Return <em>an array </em><code>answer</code><em> where </em><code>answer[i]</code><em> is the number of <strong>different</strong> nodes that you will visit if you perform the process starting from node </em><code>i</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/08/31/graaphdrawio-1.png" />
<pre>
<strong>Input:</strong> edges = [1,2,0,0]
<strong>Output:</strong> [3,3,3,4]
<strong>Explanation:</strong> We perform the process starting from each node in the following way:
- Starting from node 0, we visit the nodes 0 -&gt; 1 -&gt; 2 -&gt; 0. The number of different nodes we visit is 3.
- Starting from node 1, we visit the nodes 1 -&gt; 2 -&gt; 0 -&gt; 1. The number of different nodes we visit is 3.
- Starting from node 2, we visit the nodes 2 -&gt; 0 -&gt; 1 -&gt; 2. The number of different nodes we visit is 3.
- Starting from node 3, we visit the nodes 3 -&gt; 0 -&gt; 1 -&gt; 2 -&gt; 0. The number of different nodes we visit is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/08/31/graaph2drawio.png" style="width: 191px; height: 251px;" />
<pre>
<strong>Input:</strong> edges = [1,2,3,4,0]
<strong>Output:</strong> [5,5,5,5,5]
<strong>Explanation:</strong> Starting from any node we can visit every node in the graph in the process.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == edges.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= edges[i] &lt;= n - 1</code></li>
	<li><code>edges[i] != i</code></li>
</ul>

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)

        # build list to track count of incoming edges for all nodes
        in_deg_cnts = [0] * n
        for a, b in enumerate(edges): in_deg_cnts[b] += 1

        # use topological sort to partition nodes into two separate groups:
        # nodes that are not part of any cycles (L), and nodes that are
        S, L = collections.deque(i for i in range(n) if in_deg_cnts[i] == 0), []
        while S:
            a = S.popleft()
            L.append(a)
            
            b = edges[a]
            in_deg_cnts[b] -= 1
            if in_deg_cnts[b] == 0: S.append(b)
        
        # find answer for all nodes that are part of a cycle (still have >0 incoming edges)
        res, checked = [0] * n, set()
        for i in (i for i, idc in enumerate(in_deg_cnts) if idc > 0):
            if i in checked: continue

            # run DFS to detect the cycle
            node, visited = i, set()
            while node not in visited:
                visited.add(node)
                node = edges[node]
            
            # all nodes in the current cycle have answers equaling the cycle length
            for x in visited: res[x] = len(visited)
            
            checked.update(visited)
        
        # find answer for nodes that are not part of any cycles;
        # iterate in reverse to use previously computed answers
        for x in reversed(L): res[x] = res[edges[x]] + 1

        return res
1166