Peaceful Rooks (Codeforces 1464A)
Tags: Others, dsu

You are given a $$$n \times n$$$ chessboard. Rows and columns of the board are numbered from $$$1$$$ to $$$n$$$. Cell $$$(x, y)$$$ lies on the intersection of column number $$$x$$$ and row number $$$y$$$.Rook is a chess piece, that can in one turn move any number of cells vertically or horizontally. There are $$$m$$$ rooks ($$$m < n$$$) placed on the chessboard in such a way that no pair of rooks attack each other. I.e. there are no pair of rooks that share a row or a column.In one turn you can move one of the rooks any number of cells vertically or horizontally. Additionally, it shouldn't be attacked by any other rook after movement. What is the minimum number of moves required to place all the rooks on the main diagonal?The main diagonal of the chessboard is all the cells $$$(i, i)$$$, where $$$1 \le i \le n$$$.

Input: The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^3$$$). Description of the $$$t$$$ test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ — size of the chessboard and the number of rooks ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m < n$$$). Each of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — positions of rooks, $$$i$$$-th rook is placed in the cell $$$(x_i, y_i)$$$ ($$$1 \leq x_i, y_i \leq n$$$). It's guaranteed that no two rooks attack each other in the initial placement.The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each of $$$t$$$ test cases print a single integer — the minimum number of moves required to place all the rooks on the main diagonal.It can be proved that this is always possible.

Note: Possible moves for the first three test cases:  $$$(2, 3) \to (2, 2)$$$  $$$(2, 1) \to (2, 3)$$$, $$$(1, 2) \to (1, 1)$$$, $$$(2, 3) \to (2, 2)$$$  $$$(2, 3) \to (2, 4)$$$, $$$(2, 4) \to (4, 4)$$$, $$$(3, 1) \to (3, 3)$$$, $$$(1, 2) \to (1, 1)$$$ 

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

Sample Outputs:
1
3
4
2

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def MI1():
    return map(int1, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7

def cost(su):
    d = 0
    u = su
    while 1:
        u = to[u]
        d += 1
        if u == -1 or u == su or fin[u]:
            break
        fin[u] = True
    if u == su:
        return d // 2 + 1
    return (d + 1) // 2
for _ in range(II()):
    (n, m) = MI()
    to = [-1] * (n + m)
    fin = [False] * (n + m)
    for u in range(m):
        (i, j) = MI1()
        if i == j:
            fin[u] = True
        else:
            to[m + i] = u
            to[u] = m + j
    ans = 0
    for u in range(m):
        if fin[u]:
            continue
        fin[u] = True
        ans += cost(u)
    print(ans)

Solution (Python):
def mapInput():
    return map(int, input().split())

def listInput():
    return [int(x) for x in input().split()]

def bfs(u, used, g):
    q = [[u, -1]]
    used[u] = True
    ans = False
    while len(q):
        (u, p) = q.pop()
        for v in g[u]:
            if v == p:
                continue
            if used[v]:
                ans = True
            else:
                used[v] = True
                q.append([v, u])
    return ans

def solve():
    (n, m) = mapInput()
    ans = m
    g = [[] for _ in range(m)]
    a = [[] for _ in range(n)]
    for i in range(m):
        (x, y) = mapInput()
        if x == y:
            ans -= 1
        else:
            if len(a[x - 1]):
                g[a[x - 1][0]].append(i)
                g[i].append(a[x - 1][0])
            if len(a[y - 1]):
                g[a[y - 1][0]].append(i)
                g[i].append(a[y - 1][0])
            a[x - 1].append(i)
            a[y - 1].append(i)
    used = [False] * n
    for i in range(m):
        if not used[i]:
            ans += bfs(i, used, g)
    print(ans)
if __name__ == '__main__':
    from sys import stdout, stdin
    input = stdin.readline

    def print(*args, sep=' ', end='\n'):
        args = [str(arg) for arg in args]
        stdout.write(args[0])
        for arg in args[1:]:
            stdout.write(sep)
            stdout.write(arg)
        stdout.write(end)
    t = int(input())
    for _ in range(t):
        solve()
    stdout.flush()

Solution (Python):
def mapInput():
    return map(int, input().split())

def listInput():
    return [int(x) for x in input().split()]

def bfs(u, used, g):
    q = [[u, -1]]
    used[u] = True
    ans = False
    while len(q):
        (u, p) = q.pop()
        for v in g[u]:
            if v == p:
                continue
            if used[v]:
                ans = True
            else:
                used[v] = True
                q.append([v, u])
    return ans

def solve():
    (n, m) = mapInput()
    ans = m
    g = [[] for _ in range(m)]
    a = [[] for _ in range(n)]
    for i in range(m):
        (x, y) = mapInput()
        if x == y:
            ans -= 1
        else:
            if len(a[x - 1]):
                g[a[x - 1][0]].append(i)
                g[i].append(a[x - 1][0])
            if len(a[y - 1]):
                g[a[y - 1][0]].append(i)
                g[i].append(a[y - 1][0])
            a[x - 1].append(i)
            a[y - 1].append(i)
    used = [False] * n
    for i in range(m):
        if not used[i]:
            ans += bfs(i, used, g)
    print(ans)
if __name__ == '__main__':
    from sys import stdout, stdin
    t = int(input())
    for _ in range(t):
        solve()
    stdout.flush()