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

"""

We have the same amount of nodes and edges.
Find all strongly connected components, and form a condensation graph.

In a condensation graph, each node is a strongly connected component, and there are no cycles.
A node can atleast visit all of the nodes in the scc it is contained in.

Consider the bridge edges. Bridge edges connect scc together.
If a node u has an edge u -> v that is a bridge edge, then u and v are in different sccs.

So then ans[u] = max(scc(u), 1 + ans[v]).

In the condensation graph. let u and v be different condensation graphs.
if v is reachable from u, then ans[u] = size(u) + ans[v].
for each node in u ans[node] = ans[u]. 
Except if the node has a bridge, 
in that case ans[node] = max(size(scc(node)), 1 + size(scc(node that bridge points to)))


Condensation graph is then a directly acyclic graph, meaning it can be topologically sorted.
let bottom be the bottom most node in the topoligical sort. Then ans[bottom] = size(scc(bottom)). 
Because no other node in the condensation graph is reachable.

"""
from collections import deque

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
       
        n = len(edges)
        GF, GR = [[] for _ in range(n)], [[] for _ in range(n)]

        for u,v in enumerate(edges):
            GF[u].append(v)
            GR[v].append(u)
        
        order = []
        comp = []
        vis = [0] * n
        color = 0
        nodeMap = [0] * n

        def dfs1(u):
            vis[u] = 1
            for v in GF[u]:
                if not vis[v]:
                    dfs1(v)
            order.append(u)
        
        def dfs2(u):
            vis[u] = 1
            comp.append(u)
            for v in GR[u]:
                if not vis[v]:
                    dfs2(v)
            return

        for u in range(n):
            if not vis[u]:
                dfs1(u)
        
        order = order[::-1]
        vis = [0] * n
        sccSize = []

        for u in order:
            if not vis[u]:
                dfs2(u)
                sccSize.append(len(comp))

                for v in comp:
                    nodeMap[v] = color
                color+=1
                comp = []


        adj_cond = [set() for _ in range(color)] 
        indegrees = [0] * color
        for u in range(n):
            for v in GF[u]:
                if nodeMap[v] != nodeMap[u]:
                    adj_cond[nodeMap[u]].add(nodeMap[v])
                    
        for u in range(color):
            for v in adj_cond[u]:
                indegrees[v]+=1

        order = [] #Topological ordering of the condensation graph
        queue = deque([i for i in range(color) if indegrees[i] == 0])

        while queue:
            u = queue.popleft()
            order.append(u)

            for v in adj_cond[u]:
                indegrees[v]-=1
                if indegrees[v] == 0:
                    queue.append(v)

        
        for u in order[::-1]:
            tmp = sccSize[u]
            for v in adj_cond[u]:
                tmp = max(tmp, sccSize[u] + sccSize[v])
            sccSize[u] = tmp

        

        ans = [0] * n
        vis = [0] * n
        def dfs3(u):
            vis[u] = 1
            ans[u] = sccSize[nodeMap[u]]

            for v in GF[u]:
                if nodeMap[u] != nodeMap[v]:
                    if not vis[v]:
                        dfs3(v)
                    ans[u] = max(ans[u], 1 + ans[v])
        for u in range(n):
            if not vis[u]: dfs3(u)
            
        return ans
84900