CPP Program Permutation Swaps – Advanced Graphs

  • 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