并查集

操作

• 将两个集合合并
• 询问两个元素是否在一个集合当中

朴素算法下，合并两个集合需要执行\(O(n+m)\)次；并查集可以近乎\(O(1)\)合并两个集合

基本原理

• 用树的形式维护所有集合；根节点是集合编号
• 每个节点存储父节点，p[x] 表示x的父节点

如何判断树根

• if (p[x] == x) ，根节点的父节点是它本身

如何求x的集合编号

• while(p[x] != x) x = p[x]
• 路径压缩? ：往上走找到根节点把路径所有点都指向根节点

如何合并两个集合 ? 记住模板

• p[x] = y，将一颗树根节点插到另一棵树的某个位置

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

如何维护集合元素个数（携带额外信息）

• 见837题

836 ?

836. 合并集合 - AcWing题库

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int p[N];

// ^ 返回x祖宗节点 + 路径压缩
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;

    while (m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'M') {
            p[find(a)] = find(b);
        } else {
            if (find(a) == find(b))
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

837 ??

837. 连通块中点的数量 - AcWing题库

保证根节点的nums有意义

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int p[N], nums[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        nums[i] = 1;
    }
    while (m--) {
        string op;
        int a, b;
        cin >> op;
        if (op == "C") {
            cin >> a >> b;
            // ^ 特判
            if (find(a) == find(b)) continue;
            // ^ 先算元素个数再合并
            nums[find(b)] += nums[find(a)];
            p[find(a)] = find(b);
        } else if (op == "Q1") {
            cin >> a >> b;
            if (find(a) == find(b))
                puts("Yes");
            else
                puts("No");
        } else if (op == "Q2") {
            cin >> a;
            cout << nums[find(a)] << endl;
        }
    }
    return 0;
}

240 ???

240. 食物链 - AcWing题库

确定每个动物跟领袖（n对1）的关系，而不是动物跟动物（n对n）的关系

维护每个节点与根节点的距离（x吃y，y到x距离是1），然后 % 3 判断类型。初始化每个节点都是0，各自一类。

• 余1：可以吃根节点
• 余2：可以被根节点吃
• 余0：与根节点是同类

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int p[N], d[N];

int find(int x) {
    if (p[x] != x) {
        // 递归处理所有祖宗节点，并更新到根的距离
        int t = find(p[x]);
        // d[x] 等于 x到父的距离 + 父到根的距离（递归处理完了）
        d[x] += d[p[x]];
        // x 的父修改为根节点，路径优化
        p[x] = t;

        // // 记录旧的父
        // int u = p[x];
        // // 路径压缩，新父根节点
        // p[x] = find(p[x]);
        // // x到根的距离等于x到旧父距离加上旧父到根的距离
        // d[x] += d[u];
    }
    return p[x];
}

int main() {
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) p[i] = i;

    int count = 0;
    while (k--) {
        char t;
        int x, y;
        cin >> t >> x >> y;
        if (x > n || y > n) {
            count++;
        } else {
            int px = find(x), py = find(y);
            if (t == '1') {
                if (px == py && (d[x] - d[y]) % 3 != 0)
                    count++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] - d[x];  // IMPORTANT
                }
            } else {
                if (x == y || px == py && (d[x] - d[y] - 1) % 3 != 0) {
                    count++;
                } else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    cout << count << endl;

    return 0;
}

堆

小根堆

每个点 <= 左右儿子，根节点就是树的最小值 。

完全二叉树用一维数组存：x 的左儿子 2x，x 的右儿子 2x+1；下标从1开始

两个操作 ?