罗罗编程学习记录
本页内容 展开查看

02.4.2.3 并查集

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.2 图论与并查集

02.4.2.3-001 并查集是什么?

一句话结论

并查集(Union-Find / Disjoint Set Union,DSU)维护一组互不相交的集合,支持查找所属集合与合并两个集合;用父指针树表示集合;适合动态连通性问题。

概念解释

  • 集合:连通分量。
  • 父指针:指向代表元(根)。
  • 操作:find、union。

原理流程

  1. 每个元素自成集合。
  2. find 找根。
  3. union 合并两棵树。

代码 / 图示

parent[i]:父节点;根 parent[root]=root

常见误区

  • 误区:并查集支持删除元素;正解:标准 DSU 不支持拆分。
  • 误区:并查集存集合内全部元素;正解:只维护父指针与代表元。

追问

  • Q:典型用途? A:连通分量、冗余边、账户合并、等式判定。
  • Q:代表元是什么? A:集合根节点,find 返回值。

02.4.2.3-002 find 怎么找根?

一句话结论

沿 parent 指针上溯到 parent[x]==x 的根;路径压缩把沿途节点直接挂到根;查找即归属判定。

概念解释

  • 父指针链。
  • 根自指。
  • 归属比较根。

原理流程

  1. 沿 parent 上溯。
  2. 到自指根停止。
  3. 比较两元素根是否相同。

代码 / 示例

int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

常见误区

  • 误区:find 比较节点本身;正解:比较根。
  • 误区:根节点父指针指向空;正解:根自指。

追问

  • Q:递归 find? A:parent[x]==find(parent[x]) 顺带压缩。
  • Q:查找复杂度? A:压缩后近似常数,见 02.4.2.3-012。

02.4.2.3-003 路径压缩怎么做?

一句话结论

find 时把路径上节点的 parent 直接改为根;隔代压缩(父指向祖父)或完全压缩(全挂根)均可;压缩后树扁平化,后续查找更快。

概念解释

  • 扁平化。
  • 沿途改挂根。
  • 隔代/完全策略。

原理流程

  1. 先找根。
  2. 回溯沿途把 parent 改根。
  3. 下次查找一跳到达。

代码 / 示例

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

常见误区

  • 误区:压缩只改当前节点;正解:沿途节点都可扁平化。
  • 误区:压缩破坏集合归属;正解:根不变,归属不变。

追问

  • Q:迭代压缩? A:先找根再二次遍历改挂。
  • Q:隔代压缩够吗? A:也有效,实现更简单。

02.4.2.3-004 union 怎么合并?

一句话结论

分别 find 两元素根;根相同已同集;不同则把一棵树根挂到另一棵树根;配合按秩/大小合并控制树高;合并后连通。

概念解释

  • 根对根合并。
  • 挂接方向。
  • 同集判断。

原理流程

  1. 找两元素根。
  2. 同根返回。
  3. 不同则挂接。

代码 / 示例

boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;
    parent[ra] = rb;
    return true;
}

常见误区

  • 误区:直接挂元素节点;正解:挂根,保持集合结构。
  • 误区:同集重复合并;正解:先判根。

追问

  • Q:合并后集合大小? A:维护 size 数组累加。
  • Q:合并失败说明什么? A:两元素已连通。

02.4.2.3-005 按秩/按大小合并怎么做?

一句话结论

合并时把矮树挂到高树下(按秩 rank),或小树挂大树下(按 size);控制树高,避免合并成链;与路径压缩配合得到近常数复杂度。

概念解释

  • 秩:树高上界。
  • 大小:节点数。
  • 控制高度。

原理流程

  1. 比较秩/大小。
  2. 小挂大。
  3. 更新秩/大小。

代码 / 示例

void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (size[ra] < size[rb]) { parent[ra] = rb; size[rb] += size[ra]; }
    else { parent[rb] = ra; size[ra] += size[rb]; }
}

常见误区

  • 误区:不比较直接挂接成链;正解:按秩/大小控制高度。
  • 误区:秩在合并后随意加一;正解:等高挂接才提升秩。

追问

  • Q:秩与实际高度? A:秩是高度上界,压缩后实际更矮。
  • Q:size 合并更直观? A:维护节点数即可。

02.4.2.3-006 并查集怎么初始化?

一句话结论

parent[i]=i,每元素独立;size 初始 1,rank 初始 0;元素编号连续 0~n-1;编号不连续需离散化映射。

概念解释

  • 初始单元素集。
  • 父自指。
  • 辅助计数初值。

原理流程

  1. 开 parent 数组。
  2. 逐元素自指。
  3. 计数初始化。

代码 / 示例

for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }

常见误区

  • 误区:parent 初始化为 0;正解:自指。
  • 误区:编号从 1 开数组越界;正解:按编号口径。

追问

  • Q:元素是字符串? A:哈希映射到整数下标。
  • Q:动态加元素? A:懒初始化,find 时自建。

02.4.2.3-007 怎么用并查集统计连通分量?

一句话结论

初始分量数 n;每次成功 union(两元素不同根)分量数减一;最终分量数即连通分量个数;等价于遍历后统计根数量。

概念解释

  • 分量初始每点。
  • 合并减一。
  • 剩余即分量。

原理流程

  1. 初始化 count=n。
  2. 成功合并 count--。
  3. 返回 count。

代码 / 示例

int count = n;
for (int[] e : edges) if (union(e[0], e[1])) count--;

常见误区

  • 误区:同集合并也减一;正解:仅成功合并减一。
  • 误区:最后数 parent 数组;正解:维护计数更直接。

追问

  • Q:网格分量? A:相邻陆地合并,初始陆地数。
  • Q:怎么验证? A:统计 find(i)==i 的根数量。

02.4.2.3-008 省份数量/朋友圈(LC 547)怎么做?

一句话结论

邻接矩阵中朋友关系 i-j 做 union;最终连通分量数即省份数;O(n²) 处理边,find/union 近常数;O(n) 父指针空间。

概念解释

  • 边:朋友关系。
  • 分量:省份。
  • 合并统计。

原理流程

  1. 初始化 n 集合。
  2. 遍历邻接矩阵合并朋友。
  3. 统计分量。

代码 / 示例

public int findCircleNum(int[][] m) {
    int n = m.length;
    DSU dsu = new DSU(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (m[i][j] == 1) dsu.union(i, j);
    return dsu.count;
}

常见误区

  • 误区:对称矩阵两侧重复合并;正解:只遍历上三角,重复合并无害但冗余。
  • 误区:对角线计入边;正解:自环不影响合并。

追问

  • Q:DFS/BFS 版本? A:外层枚举分量,见 02.4.2.1-009。
  • Q:邻接矩阵稀疏? A:并查集仍可,扫矩阵 O(n²)。

02.4.2.3-009 冗余连接(LC 684)怎么做?

一句话结论

逐条边 union;两顶点已同集则这条边是成环冗余边,返回该边;先出现的冗余边为答案;无向图并查集典型应用。

概念解释

  • 已成连通:再加边成环。
  • 顺序:记录首次冗余。
  • 无向合并两侧。

原理流程

  1. 逐条处理边。
  2. 同集返回该边。
  3. 不同集合并。

代码 / 示例

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    DSU dsu = new DSU(n + 1);
    for (int[] e : edges) {
        if (!dsu.union(e[0], e[1])) return e;
    }
    return new int[0];
}

常见误区

  • 误区:返回环上任意边;正解:按顺序第一条冗余边。
  • 误区:编号从 0;正解:题目常从 1,数组开 n+1。

追问

  • Q:有向图冗余连接? A:需判断树型/环,口径不同。
  • Q:多条冗余? A:返回第一条。

02.4.2.3-010 账户合并(LC 721)怎么用并查集?

一句话结论

邮箱映射到整数编号;同一账户内邮箱互相 union;合并后按根分组收集邮箱;字符串元素先离散化到整数再入并查集。

概念解释

  • 元素:邮箱。
  • 同账户:合并。
  • 分组:按根。

原理流程

  1. 邮箱编号映射。
  2. 同账户邮箱合并。
  3. 按根聚合排序。

代码 / 图示

email → id;同账户邮箱 union
root → 邮箱列表

常见误区

  • 误区:并查集直接存字符串;正解:映射整数编号。
  • 误区:同账户首邮箱未并入;正解:其余邮箱与首邮箱合并。

追问

  • Q:邮箱排序输出? A:分组后排序去重。
  • Q:同名不同账户? A:按邮箱关联,不按姓名合并。

02.4.2.3-011 等式方程可满足性(LC 990)怎么做?

一句话结论

a==b 先 union;a!=b 收集后校验根不同;存在不等式两端同根则不可满足;字符变量映射到 26 个整数。

概念解释

  • 相等:合并。
  • 不等:校验分离。
  • 两遍处理。

原理流程

  1. 处理所有等式合并。
  2. 校验不等式。
  3. 冲突返回 false。

代码 / 示例

public boolean equationsPossible(String[] eq) {
    DSU dsu = new DSU(26);
    for (String s : eq) if (s.charAt(1) == '=')
        dsu.union(s.charAt(0)-'a', s.charAt(3)-'a');
    for (String s : eq) if (s.charAt(1) == '!')
        if (dsu.find(s.charAt(0)-'a') == dsu.find(s.charAt(3)-'a')) return false;
    return true;
}

常见误区

  • 误区:等式不等式混在一起处理;正解:先合并等式再校验不等式。
  • 误区:字符直接入数组;正解:减 'a' 映射。

追问

  • Q:变量不止 26? A:哈希离散化。
  • Q:自反等式? A:同元素合并无害。

02.4.2.3-012 并查集复杂度是多少?

一句话结论

路径压缩 + 按秩合并下,单次 find/union 均摊近似 O(α(n)),α 为反阿克曼函数,增长极慢,工程上可视为常数;整体 m 次操作 O(m·α(n));最差不使用优化为 O(log n) 或 O(n)。

概念解释

  • α(n):反阿克曼。
  • 均摊:多次操作平均。
  • 近常数。

原理流程

  1. 压缩扁平化。
  2. 按秩控高。
  3. 均摊 α。

代码 / 图示

α(n):n≤2^65536 时 α≤4

常见误区

  • 误区:并查集严格 O(1);正解:均摊 O(α(n)),非严格常数。
  • 误区:不压缩也是 O(1);正解:裸并查集最坏 O(n)。

追问

  • Q:α(n) 为什么可忽略? A:增长慢到实际规模内为 4 以内。
  • Q:只压缩不按秩? A:均摊仍接近对数内,理论略弱。

02.4.2.3-013 路径压缩两种策略有什么区别?

一句话结论

隔代压缩:父指向祖父,一次 find 完成;完全压缩:先找根再把沿途全挂根;后者更扁平,前者实现简单;长期均摊都接近 α。

概念解释

  • 隔代:跳一级。
  • 完全:直挂根。
  • 实现取舍。

原理流程

  1. 隔代:循环中 parent[x]=parent[parent[x]]。
  2. 完全:递归回溯挂根。
  3. 下次查找更快。

代码 / 示例

// 隔代
int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

常见误区

  • 误区:隔代压缩不扁平化;正解:多次后同样变浅。
  • 误区:递归完全压缩爆栈;正解:深链可迭代两次遍历。

追问

  • Q:面试写哪种? A:递归完全压缩最直观。
  • Q:压缩后秩需要更新吗? A:秩只用于合并参考,可不重算。

02.4.2.3-014 按秩合并的秩怎么维护?

一句话结论

秩初始 0;两树等高合并后被挂树根秩加一;不等高合并秩不变;秩是高度上界,路径压缩后实际高度可能更低,无需回改。

概念解释

  • 秩:高度上界。
  • 等高提升。
  • 压缩不回改。

原理流程

  1. 比较根秩。
  2. 小挂大。
  3. 等高更新秩。

代码 / 示例

if (rank[ra] < rank[rb]) parent[ra] = rb;
else if (rank[ra] > rank[rb]) parent[rb] = ra;
else { parent[rb] = ra; rank[ra]++; }

常见误区

  • 误区:每次合并秩都加一;正解:仅等高挂接提升。
  • 误区:压缩后把秩降回实际高度;正解:秩作上界保留即可。

追问

  • Q:按 size 合并不用秩? A:用节点数比较,更直观。
  • Q:秩最大多少? A:O(log n)。

02.4.2.3-015 并查集与 DFS/BFS 怎么选型?

一句话结论

只判连通、动态合并、离线边集归并用并查集,近常数操作;需要遍历路径、染色、距离、环上节点细节用 DFS/BFS;并查集不保存边顺序与路径。

概念解释

  • DSU:连通归属。
  • 遍历:路径与状态。
  • 能力边界。

原理流程

  1. 看是否只问连通。
  2. 看是否需要路径/距离。
  3. 选结构。

代码 / 图示

连通/合并:DSU
路径/距离/染色:DFS/BFS

常见误区

  • 误区:并查集能求最短路径;正解:只维护连通。
  • 误区:需要拆分时还用 DSU;正解:标准 DSU 不支持拆分。

追问

  • Q:离线并查集? A:边按权排序后逐步合并,如 Kruskal。
  • Q:可持久化并查集? A:进阶,保存历史版本。

02.4.2.3-016 网格图怎么用并查集?

一句话结论

格子坐标 (i,j) 编码为 i*n+j;相邻陆地格子 union;初始分量数为陆地数,成功合并递减;省去网格 DFS 递归栈。

概念解释

  • 坐标编码。
  • 邻居合并。
  • 分量计数。

原理流程

  1. 编码一维下标。
  2. 遍历格子合并右/下邻居。
  3. 统计分量。

代码 / 示例

int id = i * n + j;
if (陆地右侧) union(id, id + 1);
if (陆地下方) union(id, id + n);

常见误区

  • 误区:编码越界;正解:边界内合并。
  • 误区:非陆地也入集;正解:跳过水域。

追问

  • Q:岛屿数量 DSU 版? A:本框架实现。
  • Q:网格规模大? A:一维数组省二维映射。

02.4.2.3-017 集合大小怎么维护?

一句话结论

size 数组根节点存集合大小,初始 1;合并时大树累加小树 size;查询某集合大小取根的 size;非根节点 size 无意义。

概念解释

  • 大小存根。
  • 合并累加。
  • 非根无效。

原理流程

  1. 初始 size=1。
  2. 合并根累加。
  3. 查询先 find 根。

代码 / 示例

int sizeOf(int x) { return size[find(x)]; }

常见误区

  • 误区:读非根 size;正解:先 find 根。
  • 误区:合并不累加 size;正解:根大小更新。

追问

  • Q:最大集合? A:遍历根读 size 取最大。
  • Q:size 与秩区别? A:size 节点数,秩高度上界。

02.4.2.3-018 并查集有哪些边界用例?

一句话结论

单元素、无边、自环、重复边、两元素、完全连通、编号不连续、字符串元素;判空、离散化与重复合并口径。

概念解释

  • 空与最短。
  • 重复边。
  • 非整数元素。

原理流程

  1. 空集返回默认。
  2. 单元素自成集。
  3. 字符串先映射。

代码 / 图示

n=1 / 无边
自环 union 自身
邮箱/账户字符串

常见误区

  • 误区:重复边重复减分量;正解:同集合并失败不减。
  • 误区:字符串直接做下标;正解:离散化。

追问

  • Q:自环 union? A:find 相同,返回 false。
  • Q:空边集? A:分量数等于元素数。

02.4.2.3-019 并查集复杂度怎么汇报?

一句话结论

初始化 O(n);m 次 union/find 均摊 O(m·α(n)),空间 O(n);不做压缩与按秩时,单次最坏 O(n);α(n) 工程近似常数。

概念解释

  • 初始化线性。
  • 操作均摊 α。
  • 辅助线性。

原理流程

  1. 标注元素数 n。
  2. 操作次数 m。
  3. 分列优化前后口径。

代码 / 图示

优化后:O(m·α(n)) / O(n)
裸 DSU:单次 O(n) 最坏

常见误区

  • 误区:并查集 O(m log n);正解:双优化均摊 O(m·α(n))。
  • 误区:空间 O(1);正解:父指针与计数 O(n)。

追问

  • Q:面试写 α 还是 O(log n)? A:双优化答 α(n),说明近似常数。
  • Q:递归 find 栈深? A:压缩前可能 O(n),深链改迭代。

02.4.2.3-020 并查集常见变体有哪些?

一句话结论

连通分量、冗余连接、账户合并、等式判定、网格岛屿、Kruskal 最小生成树、区间合并、朋友关系分组;主线是 find 根 + union 合并,按题维护大小/计数。

概念解释

  • 框架:DSU。
  • 附加:size、count、分组。
  • 场景变体。

原理流程

  1. 元素离散化编号。
  2. 边/关系合并。
  3. 按根聚合结果。

代码 / 图示

连通:count
分组:根映射列表
生成树:合并时计边权

常见误区

  • 误区:变体题脱离 DSU 硬写遍历;正解:连通类优先 DSU。
  • 误区:需要拆分关系仍用 DSU;正解:DSU 只支持合并。

追问

  • Q:Kruskal 怎么用 DSU? A:边排序后合并不成环的边,见 02.4.2.4。
  • Q:区间合并归并? A:相邻区间 union 或排序贪心。