765. Couples Holding Hands

BFS

T: O(n^2)

```java

/*
2 person in one node

index/2
*/
class Solution {
    public int minSwapsCouples(int[] row) {
        List<List<Integer>> nodes = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>(); // person id, nodes id
        for (int i = 0; i < row.length; i++) {
            map.put(row[i], i/2);
        }
        for (int i = 0; i < row.length; i+=2) {
            List<Integer> list = new ArrayList<>();
            // index/2
            if (!isCouple(row[i],row[i+1])) { // add edge (actually node i to partner node(2 partner))
                list.add(map.get(getPartner(row[i])));
                list.add(map.get(getPartner(row[i+1])));
            }
            nodes.add(list);
        }
        int count = 0;
        boolean[] visited = new boolean[row.length/2];
        for (int i = 0; i < row.length/2; i++) {
            if (!visited[i]) {
                count += bfs(nodes, visited, i);
            }
        }
        return count;
    }

    // find how many componet connect with this node[start]
    // 因為某點只跟某一些點連接, 所以每個都要走過, 去檢查連接的 node 有幾個
    // componet - 1
    private int bfs(List<List<Integer>> nodes, boolean[] visited, int start) {
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        int nodeCount = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (visited[cur]) {
                continue;
            }
            visited[cur] = true;
            nodeCount++;
        
            for (int next : nodes.get(cur)) {
                queue.offer(next);
            }
        }
        return nodeCount - 1;
    }

    // 2k, 2k+1
    private boolean isCouple(int a, int b) {
        return a != b && a/2 == b/2;
    }
    private int getPartner(int i) {
        return i%2 == 0 ? i+1 : i-1;
    }
}
```