LeetCode 765. Couples Holding Hands

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class UF {
public:
    vector<int> f;
    vector<int> size;
    int n;
    UF(int _n): n(_n), f(_n), size(_n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void _union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (size[x] < size[y])
                swap(x, y);
            f[y] = x;
            size[x] += size[y];
        }
    }
};
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        UF uf(tot);
        for (int i = 0; i < n; i += 2)
            uf._union(row[i] / 2, row[i + 1] / 2);
        unordered_map<int, int> m;
        for (int i = 0; i < tot; ++i)
            ++m[uf.find(i)];
        int ans = 0;
        // for each connected set with "sz" as size,
        // "sz - 1" would be the number of needed swaps.
        for (const auto& [_, sz] : m)
            ans += sz - 1;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        vector<vector<int>> graph(tot);
        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            graph[l].emplace_back(r);
            graph[r].emplace_back(l);
        }
        vector<bool> visited(tot, false);
        int ans = 0;
        for (int i = 0; i < tot; ++i)
            if (!visited[i]) {
                queue<int> q;
                q.push(i);
                visited[i] = true;
                int cnt = 0;
                while (!q.empty()) {
                    int x = q.front(); q.pop();
                    ++cnt;
                    for (int nx : graph[x])
                        if (!visited[nx]) {
                            q.push(nx);
                            visited[nx] = true;
                        }
                }
                ans += cnt - 1;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        vector<vector<int>> graph(tot);
        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            graph[l].emplace_back(r);
            graph[r].emplace_back(l);
        }
        vector<bool> seen(tot, false);
        int cnt = 0, ans = 0;
        function<void(int)> dfs = [&](int x) {
            ++cnt;
            for (int nx : graph[x])
                if (!seen[nx]) {
                    seen[nx] = true;
                    dfs(nx);
                };
        };
        for (int i = 0; i < tot; ++i)
            if (!seen[i]) {
                seen[i] = true;
                dfs(i);
                ans += cnt - 1;
                cnt = 0;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size(), ans = 0;
        vector<int> ptn(n); // self label -> partner label
        vector<int> pos(n); // label -> seat
        for (int i = 0; i < n; ++i) {
            ptn[i] = i ^ 1;
            pos[row[i]] = i;
        }
        for (int i = 0; i < n; ++i)
            for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {
                swap(row[i], row[j]);
                swap(pos[row[i]], pos[row[j]]);
                ++ans;
            }
        return ans;
    }
};

Reference: Java/C++ O(N) solution using cyclic swapping - LeetCode Discuss.