2021-03-16
大致题意
给你一串数字，然后告诉你每一个格子能与哪些格子中的数字交换，问你最后能不能得到给你的一组排列。
思路
对于位置i,可以与位置(i+d[i])和（i-d[i]）位置的数交换
则可以考虑把位置i可以交换的位置放入一个集合里，就想到用并查集来解决。
如样例2，合成的集合有{1,5,4,3} {2} {7,6}，则1,5,4,3位置上的数可以相互交换。
所以只要判断初始数与最终的值是否在同一集合即可。
详见代码
#include<bits/stdc++.h>
using namespace std;
int n,a[105],d[105],father[105];
int find(int x){ //找father
if(father[x]!=x) father[x]=find(father[x]);
return father[x];
}
int merge(int x,int y){ //合并为同一集合
int x1=find(x);
int y1=find(y);
father[y1]=x1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
father[i]=i; //初始化
}
for(int i=1;i<=n;i++){
scanf("%d",&d[i]); //考虑是否越界
if(i-d[i]>0) merge(i,i-d[i]); //把第i个元素能到的格子合并为同一集合
if(i+d[i]<=n) merge(i,i+d[i]);
}
for(int i=1;i<=n;i++){
if(find(i)!=find(a[i])){ //判断是否在同一集合里
printf("NO\n"); //只要有一个点不行就输出NO
return 0;
}
}
printf("YES\n");
return 0;
}
完结撒花~~~~