# 765. Couples Holding Hands

## BFS

T: O(n^2)

````java
```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;
    }
}
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/765.-couples-holding-hands.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.