bipartite graph decision

• OK if the DFS paints over and no discrepancies occur.

• Bipartite graph decision with UnionFindTree - noshi91’s memo

  • UnionFind
  • Since the “if and only if u is red, then v is blue” diff relation holds for sides u and v, UnionFind can be used to determine the sufficiency of the relation.

---

This page is auto-translated from /nishio/二部グラフ判定 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.