查看“︁05-算法模板/08-并查集”︁的源代码


并查集是一种用于维护'''集合合并'''和'''查询元素所属集合'''的数据结构。

== 基础模板 ==

<syntaxhighlight lang="cpp">
const int MAXN = 100005;
int fa[MAXN];

void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x != y)
        fa[x] = y;
}
</syntaxhighlight>

== 按秩合并优化 ==

<syntaxhighlight lang="cpp">
int fa[MAXN], siz[MAXN];

void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i, siz[i] = 1;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (siz[x] < siz[y])
        swap(x, y);
    fa[y] = x;
    siz[x] += siz[y];
}
</syntaxhighlight>

== 带权并查集 ==

维护每个节点到根节点的关系（如距离）：

<syntaxhighlight lang="cpp">
int fa[MAXN], dis[MAXN];

void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i, dis[i] = 0;
}

int find(int x)
{
    if (fa[x] != x)
    {
        int root = find(fa[x]);
        dis[x] += dis[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}

void merge(int x, int y, int w) // x 到 y 的距离为 w
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
    {
        fa[fx] = fy;
        dis[fx] = dis[y] + w - dis[x];
    }
}
</syntaxhighlight>

== 常见应用 ==

- 判断图连通性
- Kruskal 最小生成树算法
- 维护朋友敌人关系（扩展域并查集）
- 区间染色问题

== 时间复杂度 ==

- 路径压缩 + 按秩合并：均摊 <math>O(\alpha(n))</math>，其中 <math>\alpha</math> 为阿克曼函数的反函数，近似 <math>O(1)</math>
- 仅路径压缩或仅按秩合并：<math>O(\log n)</math>


[[Category:算法模板]]
[[Category:三三文档]]