力扣765题：情侣牵手问题的并查集解法

一、题目解读

力扣765题要求在一个座位数组中，每对情侣需相邻而坐。给定n对情侣的初始座位安排（偶数长度数组），需通过最小次数的交换操作，使所有情侣成为相邻座位。

二、并查集完整代码

class UnionFind { // 并查集（Union-Find）数据结构
public:
    vector<int> parent; // 存储每个元素的父节点（用于表示集合）

    // 构造函数：初始化并查集，包含n个独立集合
    UnionFind(int n) {
        parent.resize(n);
            for (int i = 0; i < n; ++i) {
            parent[i] = i; 
        }
    }

    // 查找函数：查找元素x的根节点（带路径压缩优化）
    int find(int x) {
        if (parent[x]!= x) { 
            // 递归查找父节点的根，并将x直接指向根节点（路径压缩）
            parent[x] = find(parent[x]); 
        }
        return parent[x]; 
    }

    // 合并函数：将x和y所在的集合合并
    void unite(int x, int y) {
        // 将x的根节点和y的根节点合并（即让x的根节点指向y的根节点）
        parent[find(x)] = find(y);
    }
};

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size() / 2; 
        UnionFind uf(n); // 创建并查集，初始化n个独立集合

        // 将每对情侣的ID加入并查集（处理原始座位）
        for (int i = 0; i < 2 * n; i += 2) { 
            int a = row[i] / 2;
            int b = row[i + 1] / 2; 
            if (a!= b) { // 如果当前两人不是同一对情侣（需要交换）
                uf.unite(a, b); 
            }
        }

        // 统计每个集合的大小（即需要交换的次数）
        unordered_map<int, int> count; 
        for (int i = 0; i < n; ++i) {
            count[uf.find(i)]++; // 统计每个根节点出现的次数（即集合大小）
        }

        int res = 0; // 总交换次数
        for (auto& [root, size] : count) { 
            // 每个集合需要交换的次数 = 集合大小 - 1（最后一对无需交换）
            res += size - 1; 
        }
        return res;
    }
};