TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5616
  • 题目
  • P5616交换
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    何老板给你一个整数数列$P$,$P$是数字$1$到$N$的一个排列。
    何老板给你$M$对整数:\((X_1,Y_1),(X_2,Y_2),...,(X_M,Y_M)\)
    何老板允许你进行任意次下面操作:
      从$M$对数字中任选一对 \((Xi,Yi)\) ,交换 \(P_{Xi}\)\(P_{Yi}\) 的值
    何老板想知道,你最多能使$P$中有多少个位置满足$P_i=i$。

    输入格式

    第一行,两个整数$N$和$M$
    第二行,$N$个空格间隔的整数,表示$P_1,P_2,...,P_N$
    接下来$M$行,每行两个整数,表示给出的数字对

    输出格式

    一个整数,表示最多能有多少个位置满足$P_i=i$

    样例输入 1

    5 2
    5 3 1 4 2
    1 3
    5 4

    样例输出 1

    2  

    样例说明:
    执行一次(1,3)对应的操作,将P1和P3交换,得到数列1 3 5 4 2
    数列中P1=1,P4=4

    样例输入 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

    8

    样例输入 4

    5 1
    1 2 3 4 5
    1 5

    样例输出 4

    5

    提示

    \(2≤N≤10^5\)
    \(1≤M≤10^5\)
    \(1≤X_i,Y_i≤N\)
    \(X_i\ ≠\ Y_i\)
    \(M\) 个数字对中,不存在相同的数字对


    来源  arc097D - Equals