Double Sort II (Codeforces 1783F)
Tags: Others, graph matchings

You are given two permutations $$$a$$$ and $$$b$$$, both of size $$$n$$$. A permutation of size $$$n$$$ is an array of $$$n$$$ elements, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. The elements in each permutation are indexed from $$$1$$$ to $$$n$$$.You can perform the following operation any number of times:  choose an integer $$$i$$$ from $$$1$$$ to $$$n$$$;  let $$$x$$$ be the integer such that $$$a_x = i$$$. Swap $$$a_i$$$ with $$$a_x$$$;  let $$$y$$$ be the integer such that $$$b_y = i$$$. Swap $$$b_i$$$ with $$$b_y$$$. Your goal is to make both permutations sorted in ascending order (i. e. the conditions $$$a_1 < a_2 < \dots < a_n$$$ and $$$b_1 < b_2 < \dots < b_n$$$ must be satisfied) using minimum number of operations. Note that both permutations must be sorted after you perform the sequence of operations you have chosen.

Input: The first line contains one integer $$$n$$$ ($$$2 \le n \le 3000$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$; all $$$a_i$$$ are distinct).The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$; all $$$b_i$$$ are distinct).

Output: First, print one integer $$$k$$$ ($$$0 \le k \le 2n$$$) — the minimum number of operations required to sort both permutations. Note that it can be shown that $$$2n$$$ operations are always enough.Then, print $$$k$$$ integers $$$op_1, op_2, \dots, op_k$$$ ($$$1 \le op_j \le n$$$), where $$$op_j$$$ is the value of $$$i$$$ you choose during the $$$j$$$-th operation.If there are multiple answers, print any of them.


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

2
1 2
1 2

4
1 3 4 2
4 3 2 1

Sample Outputs:
1
2

0

2
3 4

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

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]

def add_edge(u, v, c):
    G[u].append([v, c, len(G[v]), 1])
    G[v].append([u, 0, len(G[u]) - 1, 0])
    return

def bfs(s):
    (q, k) = ([s], 0)
    dist = [inf] * l
    dist[s] = 0
    while len(q) ^ k:
        i = q[k]
        di = dist[i]
        for (j, c, _, _) in G[i]:
            if not dist[j] ^ inf and c:
                dist[j] = di + 1
                q.append(j)
        k += 1
    return dist

def dfs(dist, s, t, nowe):
    mi = [inf] * l
    st = [s]
    se = set()
    se.add(s)
    d = []
    while st:
        u = st[-1]
        if u == t:
            st.pop()
            break
        if nowe[u] < len(G[u]):
            (v, c, _, _) = G[u][nowe[u]]
            if c and (not dist[v] ^ dist[u] + 1) and (not v in se):
                st.append(v)
                d.append(nowe[u])
                se.add(v)
                mi[v] = min(mi[u], c)
            else:
                nowe[u] += 1
        else:
            se.remove(st.pop())
            if d:
                d.pop()
            if st:
                nowe[st[-1]] += 1
    return (st, d, mi[t])

def max_flow(s, t):
    ans = 0
    while True:
        dist = bfs(s)
        if not dist[t] ^ inf:
            break
        nowe = [0] * l
        while True:
            (st, d, f) = dfs(dist, s, t, nowe)
            if not f % inf:
                break
            ans += f
            for (u, i) in zip(st, d):
                G[u][i][1] -= f
                G[G[u][i][0]][G[u][i][2]][1] += f
    return ans
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
for i in range(1, n + 1):
    unite(i, a[i])
u = []
for i in range(1, n + 1):
    u.append(get_root(i))
s = list(set(u))
d = dict()
lu = len(s)
for i in range(lu):
    d[s[i]] = i
for i in range(n):
    u[i] = d[u[i]]
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
for i in range(n + 1):
    unite(i, b[i])
v = []
for i in range(1, n + 1):
    v.append(get_root(i))
s = list(set(v))
d = dict()
lv = len(s)
for i in range(lv):
    d[s[i]] = i
for i in range(n):
    v[i] = d[v[i]]
d = dict()
inf = pow(10, 9) + 1
l = lu + lv + 2
(s, t) = (l - 1, l - 2)
G = [[] for _ in range(l)]
for i in range(n):
    (ui, vi) = (u[i], v[i])
    if (ui, vi) in d:
        continue
    d[ui, vi] = i + 1
    add_edge(ui, vi + lu, 1)
for i in range(lu):
    add_edge(s, i, 1)
for i in range(lv):
    add_edge(i + lu, t, 1)
f = max_flow(s, t)
ng = [0] * (n + 1)
for i in range(lu):
    for (j, c, _, _) in G[i]:
        if j ^ s and (not c):
            ng[d[i, j - lu]] = 1
            break
ans = []
for i in range(1, n + 1):
    if not ng[i]:
        ans.append(i)
k = len(ans)
print(k)
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
import sys
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 998244353
t = 1

def match(x):
    for y in G[x]:
        if used[y[0]] == 0:
            used[y[0]] = 1
            if right[y[0]] == 0 or match(right[y[0]][0]):
                right[y[0]] = (x, y[1])
                return True
    return False
for _ in range(t):
    n = int(input())
    alist = [0] + list(map(int, input().split()))
    blist = [0] + list(map(int, input().split()))
    now = 0
    avisited = [0] * (n + 1)
    acir = [-1] * (n + 1)
    for i in range(1, n + 1):
        if avisited[i]:
            continue
        avisited[i] = 1
        acir[i] = now
        while not avisited[alist[i]]:
            i = alist[i]
            avisited[i] = 1
            acir[i] = now
        now += 1
    G = [[] for i in range(n)]
    bvisited = [0] * (n + 1)
    anow = 0
    for i in range(1, n + 1):
        if bvisited[i]:
            continue
        bvisited[i] = 1
        G[acir[i]].append((anow, i))
        while not bvisited[blist[i]]:
            i = blist[i]
            bvisited[i] = 1
            G[acir[i]].append((anow, i))
        anow += 1
    right = [0] * n
    temp = 0
    for i in range(n):
        used = [0] * n
        if match(i):
            temp += 1
    print(n - temp)
    sign = [1] * (n + 1)
    for i in range(n):
        if right[i]:
            sign[right[i][1]] = 0
    ans = []
    for i in range(1, n + 1):
        if sign[i]:
            ans.append(i)
    print(*ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
A = [int(x) - 1 for x in input().split()]
B = [int(x) - 1 for x in input().split()]

def find_cycle(arr):
    sz = 0
    comp = [-1] * N
    cycles = []
    for (i, a) in enumerate(arr):
        if comp[i] == -1:
            curr = [i]
            comp[i] = sz
            j = a
            while comp[j] == -1:
                curr.append(j)
                comp[j] = sz
                j = arr[j]
            cycles.append(curr)
            sz += 1
    return [comp, cycles]
(X, cx) = find_cycle(A)
(Y, cy) = find_cycle(B)
n = len(cx)
k = len(cy)
G = [[] for _ in range(n)]
for i in range(N):
    G[X[i]].append(Y[i])
mt = [-1] * k

def khun(v):
    if used[v]:
        return False
    used[v] = True
    for u in G[v]:
        if mt[u] == -1 or khun(mt[u]):
            mt[u] = v
            return True
    return False
for v in range(n):
    used = [False] * n
    khun(v)
match = [False] * N
for i in range(k):
    if mt[i] != -1:
        for digit in cx[mt[i]]:
            if digit in cy[i]:
                match[digit] = True
                break
res = [i + 1 for i in range(N) if not match[i]]
print(len(res))
print(' '.join(map(str, res)))