Problem 3E. 城市地铁旅行

Problem 3E. 城市地铁旅行

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 3E. 城市地铁旅行

时间限制:1s

空间限制:64MB

题目背景

\(Mrj\) 市是一个美丽的旅游城市,拥有很多美丽的景区。

\( Mrj \) 市旅游部为方便市民和游客在景点间旅行,兴修大量地铁线。并且为了节省经费,要求: 每个景区有且仅有一条从该景区出发的单向地铁线。

酷爱旅行的 \( tsingpig \) 将乘坐出租车到达某个景区,在游览完该景区后乘坐地铁,前往其他景区。她拿到了\( Mrj \) 市的地铁线路布局规划图,她希望知道从任意一个景区出发,乘坐地铁能够游览的最多景区数量。

题目描述

已知\( Mrj \) 市拥有 \( n \) 个旅游景区。

给定\( Mrj \) 地铁线路规划图 \(map[n]\) ,其中\( map[i] \) 表示从景区 \(i\) 出发的单向地铁线通往景区 \(map[i]\), 并且保证其合法性(即\( map[i] \in [0,n-1]\))。

请你帮助 \( tsingpig \) 求解从每个景区出发、乘坐地铁进行城市旅行能够游览的 最大不重复 景区数量(包括出发景区)。

例如下图是一个\(Mrj\) 市可能的地铁线路规划图。

image.png

请注意:

  • 首先,可以很明显的发现,地铁规划图一定有且仅有 \(n\) 条地铁线路。
  • 其次,规划图是允许 \(map[i] == i\) 的。你可以看成没有从该景区 出发 的地铁线,也可以理解为该景区有一条从自己出发回到自己的环。
  • 另外,地铁规划图是一个有向图,其对应的无向图未必是连通的。你可以认为每一个连通分量是\( Mrj \) 市的一个独立区,它的地铁线路和其他区域显然没有连接。
  • 最后,请你计算的结果中不要重复计算相同的景区,也就是说 \(tsingpig\) 不希望重复游览相同的景区。

输入格式

  • 第一行正整数\(n\),表示城市有\(n\) 个旅游景区。
  • 第二行\(n\) 个数,构成地铁线路规划图 \(map[n]\) ,其中\( map[i] \) 表示从景区 \(i\) 出发的地铁线通往景区 \(map[i]\), 并且保证其合法性(即\( map[i] \in [0,n-1]\))

输出格式

输出\(n\) 个数,第 \(i\) 个数表示 从 \(i\) 景区出发,能够游览的 最大不重复 景区数量(包括出发景区)。

样例输入 1

5
1 2 3 4 0

样例输出 1

5 5 5 5 5

样例输入 2

5
1 2 0 0 4

样例输出 2

3 3 3 4 1

解释:对于景区4,只有一条从自己出发回到自己的地铁线(或者理解成没有修建从景区4出发的地铁线),所以游览的景区数量是1

样例输入 3

75
1 38 45 3 5 63 69 13 22 15 14 28 49 74 25 12 18 36 62 53 40 7 17 60 41 61 68 73 39 67 65 8 72 48 64 43 57 19 32 55 51 9 20 47 10 6 35 16 31 30 21 70 29 37 23 71 27 33 52 56 11 24 54 26 0 34 2 42 50 59 4 58 66 46 44 

样例输出 3

63 63 63 1 63 63 63 63 8 63 63 63 63 63 63 63 63 8 63 3 63 63 8 63 63 63 63 63 63 63 63 8 63 8 63 63 8 3 63 63 63 63 63 63 63 63 63 63 8 63 63 63 63 3 63 63 63 8 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 

数据范围及限制

对于60%的数据,\( n \in [1,1000]\)

对于100%的数据,\( n \in [1,10^6]\)

2023秋 悬赏令第三周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-10-22 18:30
结束于
2023-10-29 00:00
持续时间
149.5 小时
主持人
参赛人数
85