AT_arc097_b.[ABC097D] Equals

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个将 $1$ 到 $N$ 的整数重新排列得到的排列 $p_1, p_2, \ldots, p_N$ 。另外，给定 $M$ 对整数对，每对为 $(x_1, y_1), (x_2, y_2), \ldots, (x_M, y_M)$ ，其中 $1 \leq x_j, y_j \leq N$ 。AtCoDeer 君希望通过任意次数地对排列 $p$ 进行如下操作，使得满足 $p_i = i$ 的 $i$ 的数量（ $1 \leq i \leq N$ ）最大。

选择一个 $1 \leq j \leq M$ ，交换 $p_{x_j}$ 和 $p_{y_j}$ 。

请你求出通过若干次操作后，满足 $p_i = i$ 的 $i$ 的最大可能数量。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$p_1$ $p_2$ $\ldots$ $p_N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_M$ $y_M$

输出格式

输出通过操作后，满足 $p_i = i$ 的 $i$ 的最大可能数量。

输入输出样例

输入#1
```
5 2
5 3 1 4 2
1 3
5 4
```
输出#1
```
2
```
输入#2
```
3 2
3 2 1
1 2
2 3
```
输出#2
```
3
```

输入#3

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

输出#3

输入#4
```
5 1
1 2 3 4 5
1 5
```
输出#4
```
5
```

说明/提示

限制条件

$2 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$p$ 是 $1$ 到 $N$ 的一个排列
$1 \leq x_j, y_j \leq N$
$x_j \neq y_j$
如果 $i \neq j$ ，则 $\{x_i, y_i\} \neq \{x_j, y_j\}$
所有输入均为整数

样例解释 1

选择 $j=1$ 进行操作后， $p$ 变为 1 3 5 4 2，这是最优情况，因此答案为 $2$ 。

样例解释 2

例如，依次选择 $j=1$ ， $j=2$ ， $j=1$ 进行操作后， $p$ 变为 1 2 3，显然这是最优情况。注意，同一个 $j$ 可以被多次选择。

样例解释 4

无需进行任何操作。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页