Header Ad

HackerEarth Permutation Swaps problem solution

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


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 ewrgrg

typedef 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<<"NO\n";
return ;
}
}

cout<<"YES\n";
}

int main() {

int test;
cin>>test;
while (test--) {
solve();
}
return 0;
}

Post a Comment

0 Comments