题解 CF28B 【pSort】

SmallTownKid · 2020-08-10 18:23:38 · 题解

看了其他题解的分析，自己思考一番之后想出了一个很简单的思路。

这个题的关键就在于 如何想出要使用并查集。

我们知道，如果 a 可以推出 b，b 可以推出 c，那么 a 也可以推出 c，并查集就是维护这样一种具有传递以及集合关系的数据结构。

举个例子，1 可以和 3 交换，3 可以和 5 交换，那么 1,3,5 之间就可以搞出全排列来，这个非常显然。那么只要 n 个数在同一个集合内，那么这n个数的位置可以随意互换。

所以，要判断 i 可以不可以到 a_i 的位置上就判断 i 和 a_i 在不在一个集合内就可以了，因为如果 i 和 a_i 在同一个集合内，这两个数位置就可以互换。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,fa[100010],a[100010];
int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
    fa[find(x)]=find(y);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        fa[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int d;
        scanf("%d",&d);
        if(i-d>0) unionn(i,i-d);
        if(i+d<=n) unionn(i,i+d);
    }
    for(int i=1;i<=n;i++)
    {
        if(find(i)!=find(a[i]))
        {
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}