使用并集查找（又名不相交集）检测图是否是二分图

Question

我正在 Spoj 上做一个问题，基本上可以简化为检测图是否是二分图。 我正在尝试使用 dfs 为图表着色，但它太慢了。 有人评论这个

没有 bfs，没有 dfs，没有二部图。简单的并查集就可以做到（确实速度很快）。 提示#1： 偶数长度的环不会影响两个节点之间的路径长度被 2 整除（哇，一个字有这么多 i）。 提示#2： （剧透） 令 dist[i] 为从 i 到 Parent[i] 的路径距离。使用 find 和 union 函数更新它。可以改进为将 dist 设为 bool 数组。

有人能解释一下他的意思吗？ 我认为他想说的是，对于每个节点，你存储节点和代表元素之间的距离。 然后，如果您尝试合并同一集中的两个节点，并且它们具有相同的奇偶校验，那么您将创建一个奇数循环，因此该图不能是二分图。 但是，我不明白这将如何实施。 如何在考虑距离的同时合并两组？ 您是否必须查看整个集合才能找到所有要更新的元素？

问题链接：https://www.spoj.com/problems/BUGLIFE/

Answer 1

给定一个表示为邻接列表（即边列表）的图，您可以确定它是否是二部的，如下所示：

• 初始化不相交集数据结构SETS，每个顶点都有一个单例集。 （如果两个顶点之间存在偶数长度的路径，那么我们最终会将这两个顶点统一到同一个集合中，除非我们首先返回 ꜰᴀʟꜱᴇ。）
• 初始化从每个顶点到ɴɪʟ的映射MAP。 （当我们检查边时，我们将使用从每个顶点到其邻居之一的映射来填充MAP。）
• 对于每条边 {u, v}：
  • 如果u和v属于SETS中的同一集合，则返回ꜰᴀʟꜱᴇ。
  • 如果 MAP[u] = ɴɪʟ，则设置 MAP[u] := v。
    否则，更新 SETS 以将 v 与 MAP[u] 统一。
  • 如果 MAP[v] = ɴɪʟ，则设置 MAP[v] := u。
    否则，更新 SETS 以将 u 与 MAP[v] 统一。
• 返回ᴛʀᴜᴇ。

Answer 2

DSU 不适合这种情况，因为如果我们采用集合并尝试在以下条件下将边映射到它们：

对于边 u,v 如果 Map[u]=NULL,Map[v]=NULL 我们无法确保一个随机分配给出最佳着色，因为有时选择所选情况不能为整个图着色，但另一种情况可以为它着色。所以我们需要检查两种情况为图表着色

1. u=>set1 和 v=>set2
2. u=>set2 和 v=>set1

几乎需要指数时间复杂度，比通常的 DFS 差得多。所以 DSU 并没有为这个问题提供更好的解决方案