Cross Swapping (Codeforces 1713E)
Tags: Greedy, 2-sat

You are given a square matrix $$$A$$$ of size $$$n \times n$$$ whose elements are integers. We will denote the element on the intersection of the $$$i$$$-th row and the $$$j$$$-th column as $$$A_{i,j}$$$.You can perform operations on the matrix. In each operation, you can choose an integer $$$k$$$, then for each index $$$i$$$ ($$$1 \leq i \leq n$$$), swap $$$A_{i, k}$$$ with $$$A_{k, i}$$$. Note that cell $$$A_{k, k}$$$ remains unchanged.For example, for $$$n = 4$$$ and $$$k = 3$$$, this matrix will be transformed like this:  The operation $$$k = 3$$$ swaps the blue row with the green column. You can perform this operation any number of times. Find the lexicographically smallest matrix$$$^\dagger$$$ you can obtain after performing arbitrary number of operations.$$${}^\dagger$$$ For two matrices $$$A$$$ and $$$B$$$ of size $$$n \times n$$$, let $$$a_{(i-1) \cdot n + j} = A_{i,j}$$$ and $$$b_{(i-1) \cdot n + j} = B_{i,j}$$$. Then, the matrix $$$A$$$ is lexicographically smaller than the matrix $$$B$$$ when there exists an index $$$i$$$ ($$$1 \leq i \leq n^2$$$) such that $$$a_i < b_i$$$ and for all indices $$$j$$$ such that $$$1 \leq j < i$$$, $$$a_j = b_j$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the size of the matrix.The $$$i$$$-th line of the next $$$n$$$ lines contains $$$n$$$ integers $$$A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$$$ ($$$1 \le A_{i, j} \le 10^9$$$) — description of the matrix $$$A$$$.It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, print $$$n$$$ lines with $$$n$$$ integers each — the lexicographically smallest matrix.

Note: Note that in every picture below the matrix is transformed in such a way that the blue rows are swapped with the green columns.In the first test case, we can perform $$$1$$$ operation for $$$k = 3$$$. The matrix will be transformed as below:    In the second test case, we can perform $$$2$$$ operations for $$$k = 1$$$ and $$$k = 3$$$:      

Sample Inputs:
2
3
2 1 2
2 1 2
1 1 2
4
3 3 1 2
1 1 3 1
3 2 3 2
2 3 3 1

Sample Outputs:
2 1 1
2 1 1
2 2 2
3 1 1 2
3 1 2 1
3 3 3 3
2 3 2 1

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def find_root(root_dict, x):
    L = []
    while x != root_dict[x]:
        L.append(x)
        x = root_dict[x]
    for y in L:
        root_dict[y] = x
    return x

def process(A):
    n = len(A)
    root_dict = [i for i in range(2 * n)]
    for i in range(n):
        for j in range(i + 1, n):
            if A[i][j] < A[j][i]:
                edge_type = 0
            elif A[i][j] > A[j][i]:
                edge_type = 1
            else:
                edge_type = 2
            if edge_type < 2:
                i1 = find_root(root_dict, i)
                j1 = find_root(root_dict, j)
                if i1 >= n:
                    i2 = i1 - n
                else:
                    i2 = i1 + n
                if j1 >= n:
                    j2 = j1 - n
                else:
                    j2 = j1 + n
                if j1 not in [i1, i2]:
                    if edge_type == 0:
                        root_dict[j1] = i1
                        root_dict[j2] = i2
                    elif edge_type == 1:
                        root_dict[j1] = i2
                        root_dict[j2] = i1
    for i in range(n):
        if find_root(root_dict, i) >= n:
            for k in range(n):
                (A[i][k], A[k][i]) = (A[k][i], A[i][k])
    for row in A:
        row = ' '.join(map(str, row))
        sys.stdout.write(f'{row}\n')
t = int(input())
for i in range(t):
    n = int(input())
    A = []
    for j in range(n):
        row = [int(x) for x in input().split()]
        A.append(row)
    process(A)

Solution (Python):
import io, os
import sys
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    n = int(input())
    matrix = []
    for _ in range(n):
        matrix.append(list(map(int, input().split())))
    group = [i for i in range(n)]

    def unionfind(root):
        son = root
        while root != group[root]:
            root = group[root]
        while son != root:
            temp = group[son]
            group[son] = root
            son = group[temp]
        return root
    neigh = [[] for _ in range(n)]
    colors = [-1 for _ in range(n)]
    op = []
    for i in range(n):
        for j in range(i + 1, n):
            if matrix[i][j] == matrix[j][i]:
                continue
            rooti = unionfind(i)
            rootj = unionfind(j)
            if rooti == rootj:
                continue
            group[max(rooti, rootj)] = min(rooti, rootj)
            if matrix[i][j] > matrix[j][i]:
                neigh[i].append([j, 1])
                neigh[j].append([i, 1])
            else:
                neigh[i].append([j, 0])
                neigh[j].append([i, 0])
    queue = deque()
    for i in range(n):
        if colors[i] >= 0:
            continue
        queue.append([i, 0])
        colors[i] == 0
        while queue:
            (index, c) = queue.popleft()
            for [nextindex, sym] in neigh[index]:
                if colors[nextindex] >= 0:
                    continue
                if sym == 1:
                    colors[nextindex] = 1 - c
                    queue.append([nextindex, 1 - c])
                else:
                    colors[nextindex] = c
                    queue.append([nextindex, c])
    for i in range(n):
        for j in range(i + 1, n):
            if colors[i] == colors[j]:
                continue
            (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j])
    for ele in matrix:
        s = ' '.join(map(str, ele))
        sys.stdout.write(s + '\n')
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def swap(k):
    for i in range(n):
        (A[i][k], A[k][i]) = (A[k][i], A[i][k])

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)
t = int(input())
for tests in range(t):
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    Group = [i for i in range(n + 1)]
    Nodes = [1] * (n + 1)
    E = [[] for i in range(n + 1)]
    for i in range(n):
        for j in range(i + 1, n):
            x = A[i][j]
            y = A[j][i]
            if x > y:
                if find(i) != find(j):
                    Union(i, j)
                    E[i].append((j, 1))
                    E[j].append((i, 1))
            elif x < y:
                if find(i) != find(j):
                    Union(i, j)
                    E[i].append((j, 0))
                    E[j].append((i, 0))
    USE = [-1] * n
    for i in range(n):
        if USE[i] == -1:
            Q = [i]
            USE[i] = 0
            while Q:
                x = Q.pop()
                for (to, c) in E[x]:
                    if USE[to] == -1:
                        USE[to] = USE[x] ^ c
                        Q.append(to)
    for i in range(n):
        for j in range(i + 1, n):
            if USE[i] ^ USE[j] == 1:
                (A[i][j], A[j][i]) = (A[j][i], A[i][j])
    for i in range(n):
        sys.stdout.write(' '.join(map(str, A[i])) + '\n')