33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:36Z

导入1个版本

←上一版本	2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

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

== 基础模板 ==

<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:三三文档]]

05-算法模板/08-并查集 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档