Couples Holding Hands

Intuition

Solution

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row) // 2
        edges = [[] for _ in range(n)]
        for i in range(n):
            p, q = row[2 * i], row[2 * i + 1]
            edges[p // 2].append(i)
            edges[q // 2].append(i)

        self.visited = [False] * n
        adj = [[] for _ in range(n)]
        for p, q in edges:
            adj[p].append(q)
            adj[q].append(p)

        ans = n
        for i in range(n):
            if not self.visited[i]:
                self.dfs(adj, i)
                ans -= 1
        return ans

    def dfs(self, adj, i):
        self.visited[i] = True
        for child in adj[i]:
            if not self.visited[child]:
                self.dfs(adj, child)