[ABC327D] Good Tuple Problem 题解

Expert_Dream · 2023-11-05 10:26:12 · 题解

分析：

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

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

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

code。