No.3650 Teleportation Cycles
タグ : / 解いたユーザー数 74
作問者 :
とある理系大学生の日常
Problem Statement
There are $N$ cities, numbered from city $1$ to city $N$.
Each city $i$ has $1$ teleporter installed, which, when used, instantly moves you one-way to city $A_i$. Note that a teleporter may lead to the same city.
Find how many "simple cycles (round-trip routes)" exist, in which you travel through some cities by teleporters and return to the original city.
Note that a round-trip route consisting of only one city (the case where moving from that city returns to the same city) also counts as one route.
More precisely, find the number of sets $S$ of cities satisfying the following conditions.
- The number of cities contained in $S$ is at least $1$.
- For any city $v$ contained in $S$, the teleporter's destination $A_v$ is also contained in $S$.
- Starting from any city contained in $S$, you can visit every city contained in $S$ exactly once and return to the original city.
Constraints
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 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
Output the number of existing round-trip routes (cycles) as an integer.
Print a newline at the end.
Sample
Sample 1
Input
4 2 3 1 4
Output
2
There is $1$ round-trip route of length $3$, cities $1 \to 2 \to 3 \to 1$,
and $1$ round-trip route of length $1$, city $4 \to 4$,
for a total of $2$.
Sample 2
Input
5 2 3 4 5 2
Output
1
Sample 3
Input
6 2 3 1 5 6 4
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。