Koxia and Game (Codeforces 1770D)
Tags: Others, graph matchings

Koxia and Mahiru are playing a game with three arrays $$$a$$$, $$$b$$$, and $$$c$$$ of length $$$n$$$. Each element of $$$a$$$, $$$b$$$ and $$$c$$$ is an integer between $$$1$$$ and $$$n$$$ inclusive.The game consists of $$$n$$$ rounds. In the $$$i$$$-th round, they perform the following moves:  Let $$$S$$$ be the multiset $$$\{a_i, b_i, c_i\}$$$.  Koxia removes one element from the multiset $$$S$$$ by her choice.  Mahiru chooses one integer from the two remaining in the multiset $$$S$$$. Let $$$d_i$$$ be the integer Mahiru chose in the $$$i$$$-th round. If $$$d$$$ is a permutation$$$^\dagger$$$, Koxia wins. Otherwise, Mahiru wins.Currently, only the arrays $$$a$$$ and $$$b$$$ have been chosen. As an avid supporter of Koxia, you want to choose an array $$$c$$$ such that Koxia will win. Count the number of such $$$c$$$, modulo $$$998\,244\,353$$$.Note that Koxia and Mahiru both play optimally.$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq {10}^5$$$) — the size of the arrays.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$${10}^5$$$.

Output: Output a single integer — the number of $$$c$$$ makes Koxia win, modulo $$$998\,244\,353$$$.

Note: In the first test case, there are $$$6$$$ possible arrays $$$c$$$ that make Koxia win — $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 3]$$$, $$$[3, 3, 2]$$$.In the second test case, it can be proved that no array $$$c$$$ makes Koxia win.

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

Sample Outputs:
6
0

Solution (Python):
import sys
sys.setrecursionlimit(2 * 10 ** 5)
if sys.implementation.name == 'pypy':
    import pypyjit
    pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict

class UnionFind:

    def __init__(self, N):
        self.parent_or_size = [-1] * N

    def root(self, x):
        if self.parent_or_size[x] < 0:
            return x
        else:
            self.parent_or_size[x] = self.root(self.parent_or_size[x])
            return self.parent_or_size[x]

    def unite(self, x, y):
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return
        if -self.parent_or_size[root_x] < -self.parent_or_size[root_y]:
            (root_x, root_y) = (root_y, root_x)
        self.parent_or_size[root_x] += self.parent_or_size[root_y]
        self.parent_or_size[root_y] = root_x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parent_or_size[self.root(x)]

    def groups(self):
        ret = defaultdict(list)
        for i in range(N):
            ret[self.root(i)].append(i)
        return [group for group in ret.values()]
input = sys.stdin.readline
MOD = 998244353
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    ans = 1
    uf = UnionFind(N + 1)
    uf2 = UnionFind(N + 1)
    for (a, b) in zip(A, B):
        if not uf.same(a, b):
            uf.unite(a, b)
            uf2.unite(a, b)
        elif not uf.same(0, a):
            uf.unite(0, a)
            if a == b:
                ans *= N
                ans %= MOD
            else:
                ans *= 2
                ans %= MOD
        else:
            ans = 0
            break
    print(ans)

Solution (Python):
U = 998244353
t = int(input(''))
N = []
S = [0]
A = []
B = []
for i in range(t):
    N.append(int(input('')))
    A += [int(x) - 1 for x in input('').split(' ')]
    B += [int(x) - 1 for x in input('').split(' ')]
    S.append(S[-1] + N[-1])
for i in range(t):
    deg = [0] * N[i]
    for j in range(N[i]):
        deg[A[S[i] + j]] += 1
        deg[B[S[i] + j]] += 1
    bad = False
    queue = []
    for j in range(N[i]):
        if deg[j] == 0:
            bad = True
            break
        if deg[j] == 1:
            queue.append(j)
    if bad:
        print(0)
        continue
    L = [[] for j in range(N[i])]
    for j in range(N[i]):
        u = A[S[i] + j]
        v = B[S[i] + j]
        L[u].append(v)
        L[v].append(u)
    sure = [0] * N[i]
    q = 0
    while q < len(queue):
        leaf = queue[q]
        deg[leaf] -= 1
        q += 1
        for v in L[leaf]:
            deg[v] -= 1
            if deg[v] == 0:
                bad = True
                q = len(queue)
                break
            if deg[v] == 1:
                queue.append(v)
    if bad:
        print(0)
        continue
    via = [u for u in range(N[i]) if deg[u] > 0]
    for u in via:
        L[u] = [v for v in L[u] if deg[v] > 0]
    ones = 0
    circs = 0
    vis = [0] * N[i]
    for q in range(N[i]):
        if not vis[q] and deg[q] > 0:
            vis[q] = 1
            if L[q] == [q, q]:
                ones += 1
            else:
                loop = 1
                last = q
                cur = L[q][0]
                while not vis[cur]:
                    vis[cur] = 1
                    loop += 1
                    if L[cur][0] == last:
                        nxt = L[cur][1]
                    else:
                        nxt = L[cur][0]
                    last = cur
                    cur = nxt
                circs += 1
    prod = 1
    for k in range(ones):
        prod = prod * N[i] % U
    for k in range(circs):
        prod = prod * 2 % U
    print(prod)

Solution (Python):
import sys
m = 998244353

class Graph:

    def __init__(self):
        self.edges = dict()

    def add(self, u, v):
        if u not in self.edges:
            self.edges[u] = {v: 1}
        elif v not in self.edges[u]:
            self.edges[u][v] = 1
        else:
            self.edges[u][v] += 1
        if u != v:
            if v not in self.edges:
                self.edges[v] = {u: 1}
            elif u not in self.edges[v]:
                self.edges[v][u] = 1
            else:
                self.edges[v][u] += 1

    def delete(self, u, v):
        self.edges[u][v] -= 1
        if self.edges[u][v] == 0:
            del self.edges[u][v]
        if len(self.edges[u]) == 0:
            del self.edges[u]
        if u != v:
            self.edges[v][u] -= 1
            if self.edges[v][u] == 0:
                del self.edges[v][u]
            if len(self.edges[v]) == 0:
                del self.edges[v]

    def freq(self, u, v):
        if u not in self.edges:
            return 0
        if v not in self.edges[u]:
            return 0
        else:
            return self.edges[u][v]
T = int(sys.stdin.readline().strip())
for t in range(0, T):
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    b = list(map(int, sys.stdin.readline().strip().split()))
    seen = set()
    todo = []
    ans = 1
    g = Graph()
    for i in range(0, n):
        g.add(a[i], b[i])
    for i in range(1, n + 1):
        if g.freq(i, i):
            ans *= n
            ans %= m
            g.delete(i, i)
            seen.add(i)
            todo.append(i)
        elif i in g.edges and len(g.edges[i]) == 1:
            todo.append(i)
        elif i not in g.edges:
            ans = 0
    while g.edges and ans > 0:
        while todo and ans > 0:
            i = todo.pop()
            if i not in g.edges:
                continue
            if i not in seen:
                j = next(iter(g.edges[i].keys()))
                ans *= g.freq(i, j)
                ans %= m
                g.delete(i, j)
                seen.add(i)
                if j in g.edges and len(g.edges[j]) == 1:
                    todo.append(j)
            while i in g.edges:
                j = next(iter(g.edges[i].keys()))
                if j in seen:
                    ans = 0
                g.delete(i, j)
                seen.add(j)
                todo.append(j)
        if g.edges and ans > 0:
            i = next(iter(g.edges.keys()))
            j = next(iter(g.edges[i].keys()))
            g.delete(i, j)
            seen.add(i)
            todo.append(i)
            if j in g.edges and len(g.edges[j]) == 1:
                todo.append(j)
            ans *= 2
            ans %= m
    print(ans % m)