B. pSort

题目链接：

http://codeforces.com/problemset/problem/28/B

题意：

给一个n，原本有个1到n按顺序排列的序列，给一个序列问，在给一个数组，表示这个位置的数可以换到pi位置，问能不能实现给的那个序列的排列。如果可以输出yes相反输出no

思路：

通过画图可知同一个集合的数字一定可以相互交换位置。所以这里使用并查集就好。

代码：

 #include<bits/stdc++.h>

 #define LL long long

 using namespace std;

 const int maxn=+;

 struct node

 {

     int to,Next;

 };

 int Head[maxn];

 node Edge[maxn*];

 int cnt=;

 int a[maxn],b[maxn],Fa[maxn];

 void add(int u,int v)

 {

     Edge[++cnt].to=v;

     Edge[cnt].Next=Head[u];

     Head[u]=cnt;

     return ;

 }

 int Find(int x)

 {

     if(x==Fa[x])

     {

         return x;

     }

     else

     {

         return Fa[x]=Find(Fa[x]);

     }

 }

 int main()

 {

     int n;

     cin>>n;

     for(int i=;i<=n;i++)

     {

         Fa[i]=i;

     }

     for(int i=;i<=n;i++)

     {

         cin>>a[i];

     }

     for(int i=;i<=n;i++)

     {

         cin>>b[i];

     }

     for(int i=;i<=n;i++)

     {

         if(i+b[i]<=n||i-b[i]>=)

         {

             int root1=Find(i);

             if(i+b[i]<=n)

             {

                 int root2=Find(i+b[i]);

                 if(root1!=root2)

                 {

                     Fa[root2]=root1;

                 }

             }

             if(i-b[i]>=)

             {

                 int root2=Find(i-b[i]);

                 if(root1!=root2)

                 {

                     Fa[root2]=root1;

                 }

             }

         }

     }

     int flag=;

     for(int i=;i<=n;i++)

     {

         int root1=Find(a[i]);

         int root2=Find(i);

         if(root1!=root2)

         {

             //cout<<i<<" "<<a[i]<<endl;

             flag=;

             break;

         }

     }

     if(flag)

     {

         cout<<"YES"<<endl;

     }

     else

     {

         cout<<"NO"<<endl;

     }

     return ;

 }

巴特西

B. pSort

最新文章

热门文章