ID: 902

Type: Default

1000ms

256MiB

Difficulty: 5

Uploaded By:

Tags>

阿里系

题目描述

塔子哥有一个长为 $n$ 的排列，并使用该排列建了一个有向图。

思路

思维题。

由于 a 数组是一个 1-n 的排列，因此对于每个 i，必然有这样的线路： i -> a[i] -> a[a[i]] -> ... -> i

所以必然是一个圈，只需要统计每个圈的大小为 $x$ ，所有圈的平方 $x^2$ 和即为答案。

时间复杂度： $O(n)$