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

  def __init__(self, graph: List[List]):
    self.graph = graph
    self.graph_reverse = self._transpose(graph)
    self.visited_vertex = [False] * len(graph)
    self.stack = []
    self.components = []

  def _transpose(self, graph: List[List[int]]) -> List[List[int]]:
    g = [[] for _ in range(len(graph))]
    for i in range(len(graph)):
      for j in graph[i]:
        g[j].append(i)
    return g

  def dfs_forward(self, node_curr: int) -> None:
    self.visited_vertex[node_curr] = True
    for node_next in self.graph[node_curr]:
      if not self.visited_vertex[node_next]:
        self.dfs_forward(node_next)

    self.stack.append(node_curr)

  def dfs_reverse(self, node_curr: int) -> None:
    self.visited_vertex[node_curr] = True
    self.components[-1].append(node_curr)
    for node_next in self.graph_reverse[node_curr]:
      if not self.visited_vertex[node_next]:
          self.dfs_reverse(node_next)

  def get_scc(self) -> List[List[int]]:
    for i in range(len(self.visited_vertex)):
      if not self.visited_vertex[i]:
        self.dfs_forward(i)

    self.visited_vertex = [False] * len(self.visited_vertex)
    while self.stack:
      i = self.stack.pop()
      if not self.visited_vertex[i]:
        self.components.append([])
        self.dfs_reverse(i)

    return self.components

  def compress_graph(self) -> List[List[int]]:
    if not self.components:
      self.get_scc()

    old_nodes = [-1] * len(self.graph)
    for i, vals in enumerate(self.components):
      for v in vals:
        old_nodes[v] = i

    compressed_graph = [set() for _ in range(len(self.components))]
    for v1, vals in enumerate(self.graph):
      v1_ = old_nodes[v1]
      for v2 in vals:
        v2_ = old_nodes[v2]
        if v1_ != v2_:
          compressed_graph[v1_].add(v2_)

    return [list(v) for v in compressed_graph]


class MaxNodePath:

  def __init__(self, weight: List[int], g: List[List[int]]):
    self.cnt = [-1] * len(g)
    self.weight = weight
    self.g = g

  def _dfs(self, node: int) -> int:
    if self.cnt[node] != -1:
      return self.cnt[node]

    res = 0
    for node_nxt in self.g[node]:
      res = max(res, self._dfs(node_nxt))
    res += self.weight[node]

    self.cnt[node] = res
    return res

  def counts(self):
    for i in range(len(self.g)):
      if self.cnt[i] == -1:
        self._dfs(i)

    return self.cnt


class Solution:
  def countVisitedNodes(self, edges: List[int]) -> List[int]:
    g = [[] for _ in range(len(edges))]
    for i in range(len(edges)):
      g[i].append(edges[i])

    scc = StronglyConnectedComponents(g)
    g_compressed = scc.compress_graph()
    weights = [len(c) for c in scc.components]
    mn = MaxNodePath(weights, g_compressed)
    cnts = mn.counts()


    res = [0] * len(edges)
    for c_id, comp_v in enumerate(scc.components):
      for v in comp_v:
        res[v] = cnts[c_id]

    return res
1950