"""765. Couples Holding Hands
https://leetcode.com/problems/couples-holding-hands/

N couples sit in 2N seats arranged in a row and want to hold hands.
We want to know the minimum number of swaps so that every couple is sitting
side by side. A swap consists of choosing any two people, then they stand up
and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the
couples are numbered in order, the first couple being (0, 1), the second
couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the
person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
Note:

len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0...len(row)-1.
"""
from typing import List


class Solution:
    def min_swaps_couples(self, row: List[int]) -> int:
        def find(x: int) -> int:
            if uf[x] != x:
                uf[x] = find(uf[x])
            return uf[x]

        def union(x: int, y: int):
            fx, fy = find(x), find(y)
            if rank[fx] < rank[fy]:
                fx, fy = fy, fx
            uf[fy] = fx
            rank[fx] += rank[fy]

        n = len(row) // 2
        uf, rank = list(range(n)), [1] * n
        for i in range(n):
            x, y = row[2 * i] // 2, row[2 * i + 1] // 2
            if x != y:
                union(x, y)
        counter = dict()
        for i in range(n):
            root = find(i)
            if root in counter:
                counter[root] += 1
            else:
                counter[root] = 1
        ans = 0
        for value in counter.values():
            ans += value - 1
        return ans
