103574: [Atcoder]ABC357 E - Reachability in Functional Graph
Description
Score : $450$ points
Problem Statement
There is a directed graph with $N$ vertices numbered $1$ to $N$ and $N$ edges.
The out-degree of every vertex is $1$, and the edge from vertex $i$ points to vertex $a_i$.
Count the number of pairs of vertices $(u, v)$ such that vertex $v$ is reachable from vertex $u$.
Here, vertex $v$ is reachable from vertex $u$ if there exists a sequence of vertices $w_0, w_1, \dots, w_K$ of length $K+1$ that satisfies the following conditions. In particular, if $u = v$, it is always reachable.
- $w_0 = u$.
- $w_K = v$.
- For every $0 \leq i \lt K$, there is an edge from vertex $w_i$ to vertex $w_{i+1}$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq a_i \leq N$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $a_1$ $a_2$ $\dots$ $a_N$
Output
Print the number of pairs of vertices $(u, v)$ such that vertex $v$ is reachable from vertex $u$.
Sample Input 1
4 2 1 1 4
Sample Output 1
8
The vertices reachable from vertex $1$ are vertices $1, 2$.
The vertices reachable from vertex $2$ are vertices $1, 2$.
The vertices reachable from vertex $3$ are vertices $1, 2, 3$.
The vertex reachable from vertex $4$ is vertex $4$.
Therefore, the number of pairs of vertices $(u, v)$ such that vertex $v$ is reachable from vertex $u$ is $8$.
Note that the edge from vertex $4$ is a self-loop, that is, it points to vertex $4$ itself.
Sample Input 2
5 2 4 3 1 2
Sample Output 2
14
Sample Input 3
10 6 10 4 1 5 9 8 6 5 1
Sample Output 3
41
Output
问题描述
有一个有向图,包含编号为1到$N$的$N$个顶点和$N$条边。
每个顶点的出度为1,从顶点$i$指向顶点$a_i$。
计算满足顶点$v$可以从顶点$u$到达的顶点对$(u, v)$的数量。
在这里,如果存在一个长度为$K+1$的顶点序列$w_0, w_1, \dots, w_K$,满足以下条件,那么顶点$v$可以从顶点$u$到达。特别是,如果$u = v$,则总是可以到达。
- $w_0 = u$。
- $w_K = v$。
- 对于每一个$0 \leq i \lt K$,都存在从顶点$w_i$到顶点$w_{i+1}$的边。
约束
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq a_i \leq N$
- 所有输入值都是整数。
输入
输入数据通过标准输入给出以下格式:
$N$ $a_1$ $a_2$ $\dots$ $a_N$
输出
打印满足顶点$v$可以从顶点$u$到达的顶点对$(u, v)$的数量。
样例输入1
4 2 1 1 4
样例输出1
8
从顶点$1$可以到达的顶点是顶点$1, 2$。
从顶点$2$可以到达的顶点是顶点$1, 2$。
从顶点$3$可以到达的顶点是顶点$1, 2, 3$。
从顶点$4$可以到达的顶点是顶点$4$。
因此,满足顶点$v$可以从顶点$u$到达的顶点对$(u, v)$的数量为8。
注意,从顶点$4$的边是一个自环,即它指向顶点$4$自身。
样例输入2
5 2 4 3 1 2
样例输出2
14
样例输入3
10 6 10 4 1 5 9 8 6 5 1
样例输出3
41