05-算法模板/08-并查集

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

基础模板

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;
}

按秩合并优化

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];
}

带权并查集

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

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];
    }
}

常见应用

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

时间复杂度

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