1713E - Cross Swapping - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
enum{N=2013};
int n,a[N][N],f[N],T;
int fd(int x){return x==f[x]?x:f[x]=fd(f[x]);}
void mg(int x,int y){f[fd(x)]=fd(y);}
int main(){
ios::sync_with_stdio(0);
cin>>T;while(T--){
cin>>n,iota(f,f+2*n,0);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];
for(int i=0;i<n;i++)for(int j=i;j<n;j++)
if(a[i][j]<a[j][i])(fd(i)^fd(j+n))?mg(i,j),mg(i+n,j+n):swap(a[i][j],a[j][i]);
else if(a[i][j]>a[j][i]&&fd(i)!=fd(j))mg(j,i+n),mg(i,j+n),swap(a[i][j],a[j][i]);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<" \n"[j==n-1];
}
}