你还在使用 DFS 染色判断二分图吗？

shinzAnmono · 2023-09-29 16:29:30 · 算法·理论

作为一个静态判断二分图的工具，DFS 染色确实很是 popular。

但是，如果让你动态判断，你还会吗？

首先，我们引入拓展域并查集的概念。

对于并查集，如果一个点只有一种形态，你们就是一个普通并查集。如果一个点有多种形态，那么他就是一个拓展域并查集。

我们可以把 u 这个结点拆分成 u_1 和 u_2，然后每次加入一条边 (u,v)，就连接 (u_1,v_2) 和 (u_2,v_1)（其实是表示白色的 u 和黑色的 v 在一个连通块中，另一个同理）。如果存在一个节点使得 u_1,u_2 在一个连通块中，那么这个图就不是二分图（因为存在了染色冲突）。

通过这个性质，我们可以动态判断二分图，这样就是一个 O(q\alpha(n)) 的做法。

由于并查集的可撤销性和可持久化性，所以还可以执行加边删边操作，时间复杂度 O(q\log n)，用途较广。

感谢 @UnyieldingTrilobite 的提醒，修改一下时间复杂度。