1 条题解

  • 0
    @ 2025-11-18 16:09:41

    这是一道典型的并查集(Disjoint Set Union, DSU)题。

    使用数组 fa[i]fa[i] 表示每个元素的父节点。 初始化时 fa[i]=ifa[i] = i

    合并操作用“按秩合并”,查询操作使用“路径压缩”,以加快后续访问。 具体操作:

    每次查询 find(a)==find(b)find(a) == find(b) 则输出 YES,否则输出 NO。 时间复杂度:O(m)O(m)

    • 1

    信息

    ID
    8
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    15
    已通过
    5
    上传者