PROBLEM LINK:
Author: Sunita Sen
Editorialist: Sunita Sen
DIFFICULTY:
MED-HARD
PREREQUISITES:
DSU
PROBLEM:
Given an array of pairs, we will have to rearrange elements such that each pair is together.
EXPLANATION:
Let us consider the size of the array as N. Then, there will N/2 number of pairs.
So we traverse pairs one by one. There could be two cases here:
- Both the elements form a pair:
Then we need not do anything here. - The elements are from different pairs:
Let us consider that elements are two different pairs a and b. We can consider that there is an edge between them. So after connecting all the edges we will find several connected components. So we will need (SizeofComponent - 1) swaps for each component.
SOLUTIONS:
Cpp Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(a, vis) memset(a, vis, sizeof(a))
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MAX 1e9
#define F first
#define S second
long find(long a, vector<long> &p, vector<long> &sz) {
return p[a] == a ? a : p[a] = find(p[a], p, sz);
}
void connect(long a, long b, vector<long> &p, vector<long> &sz) {
long pa = find(a, p, sz);
long pb = find(b, p, sz);
if (pa == pb) {
return;
}
if (sz[pa] >= sz[pb]) {
p[pb] = pa;
sz[pa] += sz[pb];
} else {
p[pa] = pb;
sz[pb] += sz[pa];
}
}
long solve(vector<long>& row) {
long n = row.size() / 2;
long nn = row.size();
vector<long> p(n), sz(n, 1);
rep(i,n)
p[i] = i;
rep(i,n) {
long a = (nn - row[i * 2]) / 2;
long b = (nn - row[(i * 2) + 1]) / 2;
connect(a, b, p, sz);
}
long ans = 0;
rep(i,n) {
if (find(i, p, sz) == i) {
ans += sz[i] - 1;
}
}
return ans;
}
signed main(){
long t = 1;
cin>>t;
while(t--){
long n;
cin>>n;
vector<long> v(n);
rep(i,n) {
cin>>v[i];
}
long ans = solve(v);
cout<<ans<<endl;
}
}