[ABC327D] Good Tuple Problem 题解

分析：

这一道题很容易发现可以用并查集来维护 （不知道为什么其他人都用了图论），\(a_i\) 与其对应的 \(b_i\) 代表着 \(a_i\) 这个集合里不能存在着 \(b_i\)。

根据只有存在两个集合，所以我们会发现，若 \(x\) 与 \(y\) 不在一个集合且 \(x\) 与 \(z\) 也不在一个集合，那么 \(x\) 和 \(y\) 就在一个集合内。然后针对可以在一个集合内的点进行并查集。到最后再判断一下每一个点 \(a_i\) 是否与 \(b_i\) 不在一个集合内，若不在，合法，否则不合法。

时间复杂度大概在 \(O(n)\) 左右，可以过去。

code。