这是一道典型的并查集(Disjoint Set Union, DSU)题。
使用数组 fa[i]fa[i]fa[i] 表示每个元素的父节点。 初始化时 fa[i]=ifa[i] = ifa[i]=i。
合并操作用“按秩合并”,查询操作使用“路径压缩”,以加快后续访问。 具体操作:
每次查询 find(a)==find(b)find(a) == find(b)find(a)==find(b) 则输出 YES,否则输出 NO。 时间复杂度:O(m)O(m)O(m)。
YES
NO
注册一个 NanXiao OpenAtom Club Online Judge 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 NanXiao OpenAtom Club Online Judge 通用账户