28B. pSort - Codeforces Solution C++

➤  Problem Link : 28B. pSort 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

int par[101];

int find(int v)
{
    if(par[v]==v)
        return v;
    return par[v]=find(par[v]);
}

int main()
{
	int n;
	cin>>n;
	int arr[n+1],fav[n+1];
	for(int i=1;i<=n;i++)
		par[i]=i;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	int p1,p2;
	for(int i=1;i<=n;i++)
	{
		cin>>fav[i];
		if(i+fav[i]<=n)
		{
			p1=find(i);
			p2=find(i+fav[i]);
			if(p1!=p2)
				par[p2]=p1;
		}
		if(i-fav[i]>0)
		{
			p1=find(i);
			p2=find(i-fav[i]);
			if(p1!=p2)
				par[p2]=p1;
		}
	}

	for(int i=1;i<=n;i++)
	{
		p1=find(i);
		p2=find(arr[i]);
		if(p1!=p2)
		{
			cout<<"NO";
			exit(0);
		}
	}
	cout<<"YES";

}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.