【C++数据结构进阶】玩转并查集：从原理到实战，C++ 实现与高频面试题全解析

索引：0 1 2 3 4 5 6 7 8 9
ufs：-4 -3 -3 2 1 2 0 0 0 1

索引：0 1 2 3 4 5 6 7 8 9
ufs：-7 0 -3 2 1 2 0 0 0 1

#include <vector>
#include <iostream>
using namespace std;

// 并查集类
class UnionFindSet {
public:
    // 构造函数：初始化并查集，每个元素自成一个集合（值为-1）
    UnionFindSet(size_t size) : _ufs(size, -1) {}

    // 查找操作：找到元素index的根节点，带路径压缩
    int FindRoot(int index) {
        // 边界检查：index必须在合法范围内
        if (index < 0 || index >= _ufs.size()) {
            throw invalid_argument("index out of range");
        }
        // 迭代实现路径压缩：找到根节点后，回溯更新路径上所有元素的父节点
        int root = index;
        // 第一步：找到根节点
        while (_ufs[root] >= 0) {
            root = _ufs[root];
        }
        // 第二步：路径压缩，将index到root路径上的所有元素直接指向root
        while (_ufs[index] >= 0) {
            int parent = _ufs[index]; // 保存当前元素的父节点
            _ufs[index] = root;       // 将当前元素的父节点更新为根节点
            index = parent;           // 继续处理下一个元素
        }
        return root;
    }

    // 合并操作：将x1和x2所在的集合合并，返回是否合并成功
    bool Union(int x1, int x2) {
        // 找到两个元素的根节点
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

        // 如果根节点相同，说明已经在同一个集合，无需合并
        if (root1 == root2) {
            return false;
        }

        // 按大小合并：将较小的集合合并到较大的集合
        // _ufs[root]为负数，绝对值是集合大小，所以比较时用“>”（因为-3 > -4，代表大小3 < 4）
        if (_ufs[root1] > _ufs[root2]) { // root1的集合更小
            swap(root1, root2); // 保证root1是较大集合的根
        }

        // 合并：更新较大集合的大小，将较小集合的根指向较大集合的根
        _ufs[root1] += _ufs[root2]; // 集合大小相加（负数相加）
        _ufs[root2] = root1;        // 小集合的根指向大集合的根

        return true;
    }

    // 统计集合个数：数组中负数的个数
    size_t Count() const {
        size_t count = 0;
        for (int e : _ufs) {
            if (e < 0) {
                ++count;
            }
        }
        return count;
    }

    // 辅助函数：打印并查集数组（用于调试）
    void PrintUFS() const {
        cout << "并查集数组状态：";
        for (int e : _ufs) {
            cout << e << " ";
        }
        cout << endl;
    }

private:
    vector<int> _ufs; // 父指针数组，存储集合关系
};

// 测试代码
int main() {
    // 初始化10个元素（编号0-9）
    UnionFindSet ufs(10);
    cout << "初始状态：" << endl;
    ufs.PrintUFS();
    cout << "当前集合个数：" << ufs.Count() << endl; // 输出10

    // 合并西安小分队（0、6、7、8）
    ufs.Union(0, 6);
    ufs.Union(0, 7);
    ufs.Union(0, 8);
    cout << "\n合并西安小分队后：" << endl;
    ufs.PrintUFS();
    cout << "当前集合个数：" << ufs.Count() << endl; // 输出8（10-3=7？不对，初始10，合并3次，减少3个集合，10-3=7）

    // 合并成都小分队（1、4、9）
    ufs.Union(1, 4);
    ufs.Union(1, 9);
    cout << "\n合并成都小分队后：" << endl;
    ufs.PrintUFS();
    cout << "当前集合个数：" << ufs.Count() << endl; // 输出6（7-2=5？哦，初始10，合并0&6（9）、0&7（8）、0&8（7）；合并1&4（6）、1&9（5），所以是5）

    // 合并武汉小分队（2、3、5）
    ufs.Union(2, 3);
    ufs.Union(2, 5);
    cout << "\n合并武汉小分队后：" << endl;
    ufs.PrintUFS();
    cout << "当前集合个数：" << ufs.Count() << endl; // 输出3（5-2=3）

    // 合并西安和成都小分队（8和1）
    ufs.Union(8, 1);
    cout << "\n合并西安和成都小分队后：" << endl;
    ufs.PrintUFS();
    cout << "当前集合个数：" << ufs.Count() << endl; // 输出2（3-1=2）

    // 查找元素9的根节点
    int root9 = ufs.FindRoot(9);
    cout << "\n元素9的根节点：" << root9 << endl; // 输出0

    // 判断元素3和7是否同属一个集合
    int root3 = ufs.FindRoot(3);
    int root7 = ufs.FindRoot(7);
    cout << "元素3的根节点：" << root3 << endl; // 输出2
    cout << "元素7的根节点：" << root7 << endl; // 输出0
    cout << "元素3和7是否同属一个集合：" << (root3 == root7 ? "是" : "否") << endl; // 输出否

    return 0;
}

// 递归实现查找（带路径压缩）
int FindRootRecursive(int index) {
    if (index < 0 || index >= _ufs.size()) {
        throw invalid_argument("index out of range");
    }
    // 递归终止条件：找到根节点（_ufs[index] < 0）
    if (_ufs[index] < 0) {
        return index;
    }
    // 路径压缩：将当前元素的父节点更新为根节点，递归查找
    _ufs[index] = FindRootRecursive(_ufs[index]);
    return _ufs[index];
}

#include <vector>
using namespace std;

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        if (n == 0) {
            return 0;
        }
        // 初始化并查集，n个城市，每个城市初始为-1
        vector<int> ufs(n, -1);

        // 查找函数（带路径压缩，lambda表达式）
        auto findRoot = [&ufs](int x) {
            int root = x;
            // 找到根节点
            while (ufs[root] >= 0) {
                root = ufs[root];
            }
            // 路径压缩
            while (ufs[x] >= 0) {
                int parent = ufs[x];
                ufs[x] = root;
                x = parent;
            }
            return root;
        };

        // 遍历矩阵，合并相连的城市
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) { // j从i+1开始，避免重复合并（i和j与j和i是一样的）
                if (isConnected[i][j] == 1) {
                    int root1 = findRoot(i);
                    int root2 = findRoot(j);
                    if (root1 != root2) {
                        // 按大小合并
                        if (ufs[root1] > ufs[root2]) {
                            swap(root1, root2);
                        }
                        ufs[root1] += ufs[root2];
                        ufs[root2] = root1;
                    }
                }
            }
        }

        // 统计集合个数（省份数量）
        int count = 0;
        for (int e : ufs) {
            if (e < 0) {
                ++count;
            }
        }
        return count;
    }
};

// 测试代码
int main() {
    vector<vector<int>> isConnected1 = {{1,1,0},{1,1,0},{0,0,1}};
    Solution sol;
    cout << "省份数量：" << sol.findCircleNum(isConnected1) << endl; // 输出2

    vector<vector<int>> isConnected2 = {{1,0,0},{0,1,0},{0,0,1}};
    cout << "省份数量：" << sol.findCircleNum(isConnected2) << endl; // 输出3

    return 0;
}

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        // 26个小写字母，初始化并查集
        vector<int> ufs(26, -1);

        // 查找函数（带路径压缩）
        auto findRoot = [&ufs](int x) {
            int root = x;
            while (ufs[root] >= 0) {
                root = ufs[root];
            }
            // 路径压缩
            while (ufs[x] >= 0) {
                int parent = ufs[x];
                ufs[x] = root;
                x = parent;
            }
            return root;
        };

        // 第一步：处理所有"=="方程，合并相等的变量
        for (const string& eq : equations) {
            if (eq[1] == '=') { // 是"=="方程
                char c1 = eq[0];
                char c2 = eq[3];
                int x = c1 - 'a'; // 转换为0-25的索引
                int y = c2 - 'a';
                int root1 = findRoot(x);
                int root2 = findRoot(y);
                if (root1 != root2) {
                    // 按大小合并
                    if (ufs[root1] > ufs[root2]) {
                        swap(root1, root2);
                    }
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }

        // 第二步：处理所有"!="方程，检查是否矛盾
        for (const string& eq : equations) {
            if (eq[1] == '!') { // 是"!="方程
                char c1 = eq[0];
                char c2 = eq[3];
                int x = c1 - 'a';
                int y = c2 - 'a';
                int root1 = findRoot(x);
                int root2 = findRoot(y);
                if (root1 == root2) { // 两个变量在同一个集合，矛盾
                    return false;
                }
            }
        }

        // 所有方程都满足
        return true;
    }
};

// 测试代码
int main() {
    vector<string> equations1 = {"a==b","b!=a"};
    Solution sol;
    cout << (sol.equationsPossible(equations1) ? "true" : "false") << endl; // 输出false

    vector<string> equations2 = {"a==b","b==c","a==c"};
    cout << (sol.equationsPossible(equations2) ? "true" : "false") << endl; // 输出true

    vector<string> equations3 = {"a==b","b!=c","c==a"};
    cout << (sol.equationsPossible(equations3) ? "true" : "false") << endl; // 输出false

    return 0;
}