1 条题解

  • 0
    @ 2026-11-15 15:58:01

    题目分析

    40 分做法

    暴力即可。

    遍历所有可能的三元组(X,Y,Z)(X,Y,Z),检查是否满足XX和YY是朋友、YY和ZZ是朋友,但XX和ZZ不是朋友。如果满足这个条件,则将XX和ZZ合并成一个集合,表示建立新的朋友关系。

    最后,我们统计并查集中集合的数量,即为可以执行操作的最大次数。

    100 分做法

    一个 ss 个点的边双连通分量,最多可以连$$\binom{s}{2} = \frac{s*(s-1)}{2}$$ 条边,对于题目给出的森林,用并查集维护连通块,连接给定的每组($$a$$,$$b$$),合并($$a$$,$$b$$)所在的两个连通块,同时统计每个连通块的边数,最大边数-现有边数=当前可以连的边数。

    • 1

    信息

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