CPP Program Permutation Swaps – Advanced Graphs

by
  • Kevin has a permutation P of N integers 1, 2, …, N, but he doesn’t like it. Kevin wants to get a permutation Q.
  • Also, he believes that there are M good pairs of integers (ai, bi). Kevin can perform the following operation with his permutation:
  • Swap Px and Py only if (x, y) is a good pair.
  • Help him and tell if Kevin can obtain permutation Q using such operations.

Input format:

  • The first line of input will contain an integer T, denoting the number of test cases.
  • Each test case starts with two space-separated integers N and M. The next line contains N space-separated integers Pi. The next line contains N space-separated integers Qi. Each of the next M lines contains two space-separated integers ai and bi.

Output format:

  • For every test case output “YES” (without quotes) if Kevin can obtain permutation Q and “NO” otherwise.

Constraints:

1 ≤ T ≤ 10
2 ≤ N ≤ 100000
1 ≤ M ≤ 100000
1 ≤ Pi, Qi ≤ N. Pi and Qi are all distinct.
1 ≤ ai < bi ≤ N

Sample Input:

2
4 1
1 3 2 4
1 4 2 3
3 4
4 1
1 3 2 4
1 4 2 3
2 4

Sample Output:

NO 
YES

Code:

#include<iostream>
#include<vector>
#include<unordered_set>
#include<iterator>
using namespace std;
void dfs(vector<int>*edges, int start, bool*visited, unordered_set<int>*component)
{
    if(visited[start])
    {
        return;
    }
    visited[start]=true;
    component->insert(start);
    for(vector<int>::iterator it=edges[start].begin(); it!=edges[start].end(); it++)
    {
        if(!visited[*it])
        {
            dfs(edges, *it, visited, component);
        }
    }
}
unordered_set<unordered_set<int>*>* getComponents(vector<int>*edges, int n)
{
    bool *visited=new bool[n];
    for(int i=0; i<n; i++)
    {
        visited[i]=false;
    }
    unordered_set<unordered_set<int>*>*output=new unordered_set<unordered_set<int>*>();
    for(int i=0; i<n; i++)
    {
        if(!visited[i])
        {
            unordered_set<int>*component=new unordered_set<int>();
            dfs(edges, i, visited, component);
            output->insert(component);
        }
    }
    return output;
}
int main()
{
    int t;//test cases
    cin>>t;
    while(t--)
    {
        int n, m;
        cin>>n>>m;
        int *p=new int [n];
        int *q=new int [n];
        for(int i=0; i<n; i++)
        {
            cin>>p[i];
        }
        for(int i=0; i<n; i++)
        {
            cin>>q[i];
        }

        //graph initiated
        vector<int>*edges=new vector<int>[n];
        for(int i=0; i<m; i++)
        {
            int a, b;
            cin>>a>>b;
            edges[a-1].push_back(b-1);
            edges[b-1].push_back(a-1);
        }
        //adjacency list completed.
        unordered_set<unordered_set<int>*>* components=getComponents(edges, n);

        unordered_set<unordered_set<int>*>::iterator it1=components->begin();
        bool flag=true;
        while(it1!=components->end())
        {
            unordered_set<int>*component=*it1;
            unordered_set<int>::iterator it2=component->begin();
            unordered_set<int>p_index_set;
            unordered_set<int>q_index_set;
            while(it2!=component->end())
            {
                p_index_set.insert(p[*it2]);
                q_index_set.insert(q[*it2]);
                it2++;
            }
            if(p_index_set!=q_index_set)
            {
                flag=false;
            }
            it1++;
        }
        if(flag)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}
Code language: C++ (cpp)

Leave a Comment