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)