题目详情
返回题库题目描述
有一个有向图，图中有N个顶点，编号为1至N，有N条边。
每个顶点的外度为1，顶点i的边指向顶点 $a_{1}$。
计算有多少对顶点(u,v)可以从顶点u到达顶点v。
这里，如果存在长度为K+1的顶点序列$w_{0}$,$w_{1}$,…,$w_{K}$且满足以下条件，则顶点v可以从顶点u到达。其中，如果是u=v，则总是可以到达。
- $w_{0}$=u.
- $w_{k}$=v.
- 对于每一个0≤i<K，都有一条从顶点$w_{i}$到顶点$w_{i+1}$的边。
输入描述
第一行一个正整数N，代表N个顶点
第二行N个正整数，代表顶点1,2,3...N 分别到顶点$a_{1}$ ，$a_{2}$，$a_{3}$.....$a_{N}$ 有一条边
数据范围：
- 1≤N≤2×$10^{5}$
- 1≤$a_{1}$≤N
输出描述
输入一个正整数，代表顶点(u,v)中顶点v可以从顶点u到达的顶点(u,v)对数。
提示
样例1解释：
顶点1可以到达的顶点是顶点1,2.
从顶点2可以到达的顶点是顶点1,2.
从顶点3出发可以到达的顶点是顶点1,2,3。
从顶点4可以到达的顶点是顶点4。
因此，从顶点u可以到达顶点v的顶点(u,v)对数为8。
注意，来自顶点4的边是一个自循环，即它指向顶点4本身。