UnionFind
Fast merging of sets and checking for common sets data structure.
It can be viewed as adding an edge to the graph and checking whether two vertices are connected or not is fast.
For a relation between N objects, if it can be decomposed into iffs, it can be described as a graph edge
For example, "x beats y" when there is a target that is either goo or chokiper is equivalent to adding 3 edges to the 3N vertex set because it can be decomposed into 3 iff's such as "x is goo iff y is chokiper".
The connected component corresponds to a solution that satisfies the condition
If not iff -> 2-SAT.
https://judge.yosupo.jp/submission/12685
prime set data structure Wikipedia
Disjoint Set Union (DSU)
Union-Find
---
This page is auto-translated from /nishio/UnionFind 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.