树论

并查集（DSU）

并查集是一种树形的数据结构。
支持两种操作：
合并：将两个子集合并成一个集合。
查找：确定某个元素处在哪个集合。

$fa[x]$ 存节点 $x$ 的父节点，下标从 $1$ 开始有效

初始化

每个节点是一个集合，每个节点的父节点是它自己。 $fa[i]=i$

1
2
for (int i = 1; i <= n; i++)
    fa[i] = i;

查找

根节点是集合的代表，查找就是找到元素所在集合的根。

  • 如果父节点等于自己，则找到了根并返回；
  • 如果还没找到根，则继续递归查找。
1
2
3
4
5
6
int find(int x)
{
    if (fa[x] == x)
        return x;
    return find(fa[x]);
}

带路径压缩的查找
在返回的路上，顺带修改，各节点的父节点为根。

1
2
3
4
5
6
int find(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]); //修改，各节点的父节点为根
}

合并

把一个集合的根指向另一个集合的根。

1
2
3
4
void unionset(int x, int y)
{
    fa[find(x)] = find(y);
}

按秩合并（启发式合并）
把小集合的根指向大集合的根。

1
2
3
4
5
6
7
8
9
10
11
12
// 记录并初始化子树的大小为1
vector<int> siz(N, 1); // 每个元素的初始规模均为1
void unionset(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y) // 两者相等不需要合并
        return;
    if (siz[x] > siz[y]) // x规模大于y规模
        swap(x, y);      // 交换x，y位置
    fa[x] = y;           // 将规模小的合并到规模大的
    siz[y] += siz[x];    // 新的规模等于二者之和
}

板子

自己版

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
const int N = 5e5;
int fa[N] = {0};
int n;                 // 节点数
vector<int> siz(N, 1); // 记录子树大小
void init()            // 初始化
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
int find(int x) // 路径压缩查找
{
    if (fa[x] == x) // 结束
        return x;
    else
        return fa[x] = find(fa[x]); // 路径压缩
}

void unionset(int a, int b) // 合并 按秩合并
{
    int x = find(a), y = find(b);
    if (x == y) // 本身处于同一集合，不需要合并
        return;
    else
    {
        if (siz[x] > siz[y]) // x树大小比y大，交换
        {
            swap(x, y);
        }
        fa[x] = y;        // 小树当儿子
        siz[y] += siz[x]; // 大小改变
    }
}

jiangly版

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
42
43
44
45
46
47
48
49
struct DSU
{
    std::vector<int> f, siz; // x的父亲为f[x] siz-子树大小

    DSU() {}
    DSU(int n)
    {
        init(n);
    }

    void init(int n) // 初始化
    {
        f.resize(n);                      // 重新指定大小
        std::iota(f.begin(), f.end(), 0); // 初始化自己的父亲为自己
        siz.assign(n, 1);                 // 初始化子树大小为1
    }

    int find(int x) // 查找
    {
        while (x != f[x]) // 未找到顶
        {
            x = f[x] = f[f[x]]; // 路径压缩
        }
        return x;
    }

    bool same(int x, int y) // 检测是否处于同一子树
    {
        return find(x) == find(y);
    }

    bool merge(int x, int y) // 合并
    {
        x = find(x);
        y = find(y);
        if (x == y) // 不需要合并
        {
            return false;
        }
        siz[x] += siz[y]; // 字数大小改变
        f[y] = x;         // 合并最顶节点
        return true;
    }

    int size(int x) // 返回子树大小
    {
        return siz[find(x)];
    }
};