Problem10396--有向图访问计数

10396: 有向图访问计数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

现有一个有向图,其中包含 n 个节点,节点编号从 0 到 n - 1 。此外,该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ,其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
想象在图上发生以下过程:
  • 你从节点 x 开始,通过边访问其他节点,直到你在 此过程 中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案,其中 answer[i] 表示如果从节点 i 开始执行该过程,你可以访问到的不同节点数。

Input

第一行包括两个整数 $n\ (2\leq n \leq 5\times 10^5)$。
第二行 $n$ 个整数,第 $i$ 个表示 edges[i]。保证 edges[i]!=i。

Output

一行包括 $n$ 个数,第 $i$ 个数表示从节点 i 开始执行该过程,你可以访问到的不同节点数。

Sample 1 Input

4
1 2 0 0

Sample 1 Output

3 3 3 4

从每个节点开始执行该过程,记录如下: 
- 从节点 0 开始,访问节点 0 -> 1 -> 2 -> 0 。访问的不同节点数是 3 。 
- 从节点 1 开始,访问节点 1 -> 2 -> 0 -> 1 。访问的不同节点数是 3 。 
- 从节点 2 开始,访问节点 2 -> 0 -> 1 -> 2 。访问的不同节点数是 3 。 
- 从节点 3 开始,访问节点 3 -> 0 -> 1 -> 2 -> 0 。访问的不同节点数是 4 。

Sample 2 Input

5
1 2 3 4 0

Sample 2 Output

5 5 5 5 5

无论从哪个节点开始,在这个过程中,都可以访问到图中的每一个节点。

HINT

LeetCode.

Source/Category

基环树