并查集

并查集模板：

#include <iostream>
#include <vector>

using namespace std;

// 初始化父节点数组
vector<int> fa;

// 查找根节点并进行路径压缩
int findParent(int x) {
    if (x == fa[x]) return x;
    return fa[x] = findParent(fa[x]);
}

// 合并两个集合
void unionSets(int x, int y) {
    fa[findParent(x)] = findParent(y);
}

// 初始化并查集
void initialize(int n) {
    fa.resize(n);
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
    }
}

int main() {
    int n = 10; // 假设有10个元素
    initialize(n);

    // 示例操作
    unionSets(1, 2);
    unionSets(3, 4);
    unionSets(2, 4);

    // 检查是否在同一个集合中
    if (findParent(1) == findParent(3)) {
        cout << "1 and 3 are in the same set." << endl;
    } else {
        cout << "1 and 3 are in different sets." << endl;
    }

    if (findParent(1) == findParent(5)) {
        cout << "1 and 5 are in the same set." << endl;
    } else {
        cout << "1 and 5 are in different sets." << endl;
    }

    return 0;
}