连通性、并查集与二分图
本节目标
从零建立并查集的 parent 森林、路径压缩与按大小合并，并用染色判断二分图。
无向图中的“是否已经连通”经常伴随不断加入边：朋友关系、城市道路和网络组件都在问两个点是否属于同一组。并查集（Disjoint Set Union, DSU）专门维护一批互不重叠的集合；二分图则是另一种连通分量问题，它要求每条边两端能被染成不同颜色。
识别信号
- 无向边持续加入，需要快速询问两点是否已在同一连通块；
- 加一条边后，若两端本已连通，这条边就是环或冗余边；
- 邻接矩阵描述“直接或间接相连”的城市、账号或节点组；
- 要把图分成两个阵营，且每条边必须跨阵营；
- 图可能不连通，不能只从顶点
0出发。
问题模型与核心不变量
从 parent 森林开始
为每个元素建立一个 parent[i]。初始化 parent[i] = i：每个元素独自是一个集合，也是一棵只有根的树。多个集合并排放在一起，就是一片 parent 森林。树根满足 parent[root] == root，并且一个集合恰好对应一棵树。
find(x) 沿着 parent 指针走到根，返回该集合唯一的代表元。于是 find(a) == find(b) 当且仅当 a、b 已连通。路径压缩在回程时把沿途节点直接改指向根：下一次查找不用再逐层爬树。
unite(a, b) 先找两个根。根相同，合并失败并返回 false，因为它们本就在同一集合；根不同，把一棵根树接到另一棵根树上，合并成功并返回 true。维护 size[root]，总是把小树接到大树，避免树长得过高。路径压缩与按大小合并一起使用后，m 次操作的均摊时间是 O(m α(n))，单次可视为近似常数；α(n) 是增长极慢的反 Ackermann 函数。
并查集只擅长加边、合并和连通查询。它不维护删边后的分裂：删除一条树边可能把一个集合拆成两个，而 parent 森林没有足够信息恢复这个分割。含删边的动态连通性应改用离线算法、可回滚并查集或更专门的数据结构。
二分图不需要 DSU。给每个点保存 color：-1 未染色、0 和 1 是两组。每个未染色分量都从颜色 0 开始 BFS；访问边 u—v 时，未染色的 v 必须染成 1 - color[u]，已染色且与 u 同色则立即矛盾。这个规则遍历全部分量后仍无矛盾，图才是二分图。
通用模板
DSU 初始化：parent[i] = i, size[i] = 1
find(x)：若 parent[x] != x，递归/迭代压缩到根；返回根
unite(a, b)：
ra = find(a), rb = find(b)
若 ra == rb：返回 false
按 size 令小根挂到大根，更新 size
返回 true
二分图 BFS：
color 全为 -1
for 每个顶点 start:
若已染色则跳过
color[start] = 0，start 入队
出队 u；检查每个邻居 v
未染色则染相反色并入队；同色则返回 false
return true
模板变体
- 连通分量计数：从
n开始，每次unite成功就减一；最后是集合数。 - 第一条成环边：顺序扫描边，第一次
unite失败时当前边就是冗余边。 - 稠密邻接矩阵：只扫描上三角
i < j，避免对称边重复合并。 - 二分图 DFS：递归传播颜色也正确；BFS 更容易显式处理每个独立分量。
- 带敌对关系的分组：可把一个点及其“相反组”编码成两个代表元，再用 DSU；基本二分图题先用直接染色更清晰。
母题序列
按必学顺序练习：
- 省份数量（必学）：把邻接矩阵中的城市边合并，计数剩余 parent 树根。
- 冗余连接（必学）：借助
unite的失败返回值定位第一条闭环边。 - 判断二分图（必学）：在每个连通分量内传播相反颜色，寻找同色边。
常见误区
find只返回父亲而非根，间接连通的节点会被误判为不同集合。- 合并前不先找根，可能把内部节点接出错误结构。
- 同根时仍减少连通块数量；重复合并并没有产生新连接。
- 不做路径压缩和按大小合并，在长链上让查询退化。
- 用并查集处理删边并期待集合自动拆开；它不支持这个操作。
- 二分图只染第一个分量，漏掉后面分量里的奇环。
- 把孤立点当异常；孤立点单独染任意一种颜色都合法。
迁移方向
只加边的“属于同一组吗”优先考虑并查集；需要一条实际路径、最短步数或删边后连通性时，改用图搜索或专门的动态结构。出现“相邻必须不同类”时，先试二染色；若出现奇环，同一套约束就不可满足。后续最小生成树会继续使用 DSU 的 unite，但目标会从“是否连通”变成“以最小代价连接”。