HackerEarth Permutation Swaps problem solution YASH PAL, 31 July 2024 In this HackerEarth Permutation Swaps problem solution 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 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. HackerEarth Permutation Swaps problem solution. #include <string>#include <vector>#include <map>#include <list>#include <iterator>#include <set>#include <queue>#include <iostream>#include <sstream>#include <stack>#include <deque>#include <cmath>#include <memory.h>#include <cstdlib>#include <cstdio>#include <cctype>#include <algorithm>#include <utility>#include <cassert>#include<complex>#include <time.h>using namespace std;#define FOR(i, a, b) for(int i=(a);i<(b);i++)#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)#define FILL(A,value) memset(A,value,sizeof(A))#define ALL(V) V.begin(), V.end()#define SZ(V) (int)V.size()#define PB push_back#define MP make_pair#define Pi 3.14159265358979#define x0 ikjnrmthklmnt#define y0 lkrjhkltr#define y1 ewrgrgtypedef long long Int;typedef unsigned long long UInt;typedef vector<int> VI;typedef pair<int, int> PII;typedef complex<double> base;const int INF = 1000000000;const int MAX = 100007;const int MAXE = 5000;const int MAXV = 20*20;const int BASE = 1000000007;const int MOD = 1000000007;vector<int> g[MAX];bool U[MAX];VI A , B;int P[MAX];int Q[MAX];void dfs(int v){ U[v] = 1; A.push_back(P[v]); B.push_back(Q[v]); FOR(i,0,g[v].size()) { if (!U[g[v][i]]) { dfs(g[v][i]); } }}int main(){ //freopen("in.txt", "r", stdin); int t; cin >> t; FOR(tt,0,t) { int n , m; cin >> n >> m; FOR(i,0,n) { U[i] = 0; g[i].clear(); } FOR(i,0,n) { cin >> P[i]; } FOR(i,0,n) { cin >> Q[i]; } FOR(i,0,m) { int a , b; scanf("%d%d" , &a , &b); --a;--b; g[a].push_back(b); g[b].push_back(a); } bool ok = 1; FOR(i,0,n) { if (!U[i]) { A.clear(); B.clear(); dfs(i); sort(ALL(A)); sort(ALL(B)); if (A != B) ok = 0; } } if (ok) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0;} Second solution #include <cstdio>#include <cassert>#include <algorithm>#include <iostream>#include <vector>#include <set>using namespace std;const int MAXN = 100100;int perm1[MAXN], perm2[MAXN], n, m;bool was[MAXN];vector<int>go[MAXN];void solve() { scanf("%d%d", &n, &m); assert(2 <= n && n <= 1E5); assert(1 <= m && m <= 1E5); set<int>s1, s2; for (int i = 1; i <= n; i++) { scanf("%d", &perm1[i]); s1.insert( perm1[i] ); } for (int i = 1; i <= n; i++) { scanf("%d", &perm2[i]); s2.insert( perm2[i] ); } if (s1.size() != n) { assert(false); } if (s2.size() != n) { assert(false); } for (int i = 1; i <= n; i++) { go[i].clear(); } for (int i = 1; i <= m; i++) { int aa, bb; scanf("%d%d", &aa, &bb); assert(1 <= aa && bb <= n); go[aa].push_back(bb); go[bb].push_back(aa); } for (int i = 1; i <= n; i++) { was[i] = false; } for (int i = 1; i <= n; i++) { if (was[i] == true) { continue; } vector<int>q; int st = 0; q.push_back(i); was[i] = true; while (st < q.size() ) { int x = q[st]; st++; for (int j = 0; j < go[x].size(); j++) { int to = go[x][j]; if (was[to] == false) { was[to] = true; q.push_back(to); } } } vector<int>v1, v2; for (int j = 0; j < q.size(); j++) { //cerr<<q[j]<<" "; v1.push_back( perm1[ q[j] ] ); v2.push_back( perm2[ q[j] ] ); } //cerr<<endl; sort(v1.begin(), v1.end() ); sort(v2.begin(), v2.end() ); if (v1 != v2) { cout<<"NOn"; return ; } } cout<<"YESn";}int main() { int test; cin>>test; while (test--) { solve(); } return 0;} coding problems