题目描述：
你有一个1到N的排列P1,P2,P3...PN，还有M对数(x1,y1),(x2,y2),....,(xM,yM),现在你可以选取任意对数，每对数可以选取任意次，然后对选择的某对数(xi,yi)进行操作，操作方式为交换xi,yi两个位置的数。最终你想要Pi=i的位置尽可能多。输出最多可以有多少个这样的位置
输入格式：
第一行输入一个整数N，第二行输入一个整数M
接下来M行每行输入一对数xi,yi
输出格式：
输出一个整数
样例输入1：
5 2
5 3 1 4 2
1 3
5 4
样例输出1：
2
样例输入2：
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
样例输出2：
8
约定：
2<=N<=105,1<=M<=105,xi!=yi
牢骚：emmm,在看到这题的第一秒我整个人就感觉不好了
记得那是我的第一场abc，报完名用fuko大佬的电脑看了开始时间，嗯，九点
后来才知道fuko大佬的电脑是东京时间QAQ
虽然三十分钟AK了，但是因为晚开了一个小时，只有四十多名orz
所以这道D题真的是影响深刻，fuko大佬大概开题后3s就口胡完了标算
是非常中（jian）规（jian）中（dan）矩（dan）的D题
下面进入题解：
考虑如果a-b能互换，b-c能互换，那么a-c也一定能互换，这其实可以扔到并查集里，到时候查询a[i]的位置与i是不是祖先相同就可以了（没错就是这么短）
代码如下：
#include<set> #include<cmath> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,a[100010],ans; struct dsu { int fa[200010],rank[200010]; void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; } } int find(int x) { if(fa[x]==x) { return x; } return fa[x]=find(fa[x]); } void union_(int x,int y) { int fx=find(x); int fy=find(y); if(fx==fy) { return ; } if(rank[fx]<rank[fy]) { fa[fx]=fy; } else { fa[fy]=fx; if(rank[fx]==rank[fy]) { rank[x]++; } } } int same(int x,int y) { return find(x)==find(y); } }b; int main() { cin>>n>>m; b.init(n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=m;i++) { int from,to; scanf("%d%d",&from,&to); b.union_(from,to); } for(int i=1;i<=n;i++) { if(b.same(a[i],i)) { ans++; } } printf("%d ",ans); }
啊，为什么3-1这么水……