<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]:
        def dfs1(v):
            used[v] = True
            for i in adjacency_list[v]:
                if not used[i]:
                    dfs1(i)
            order.append(v)

        def dfs2(v):
            used[v] = True
            component.append(v)
            if v in adjacency_list_gr:
                for i in adjacency_list_gr[v]:
                    if not used[i]:
                        dfs2(i)

        def dfs3(v):
            if not condensation[v]:
                answer[v] = component_to_size[v]
            else:
                res = 0
                for i in condensation[v]:
                    if answer[i] == -1:
                        dfs3(i)
                    res += answer[i]
                answer[v] = res + component_to_size[v]



        # edges = [1,2,0,0]
        # edges = [1, 0, 3, 2]
        adjacency_list = dict()
        adjacency_list_gr = dict()
        for i, v in enumerate(edges):
            adjacency_list[i] = adjacency_list.get(i, []) + [v]
            adjacency_list_gr[v] = adjacency_list_gr.get(v, []) + [i]

        order = []
        used = [False] * len(edges)
        for i in range(len(edges)):
            if not used[i]:
                dfs1(i)

        used = [False] * len(edges)
        node_to_component = dict()
        component_to_size = dict()
        latest_comp = 0

        for i in order[::-1]:
            if not used[i]:
                component = []
                dfs2(i)
                for j in component:
                    node_to_component[j] = latest_comp
                component_to_size[latest_comp] = len(component)
                latest_comp += 1

        condensation = dict((i, list()) for i in range(latest_comp))
        for i, v in enumerate(edges):
            if node_to_component[i] != node_to_component[v]:
                condensation[node_to_component[i]].append(node_to_component[v])

        answer = [-1] * latest_comp
        used = [False] * latest_comp
        for i in range(latest_comp):
            if not used[i]:
                dfs3(i)
        final_answer = [answer[node_to_component[i]] for i in range(len(edges))]
        return final_answer
102600