1 条题解
-
0
题目分析
40 分做法
暴力即可。
遍历所有可能的三元组,检查是否满足和是朋友、和是朋友,但和不是朋友。如果满足这个条件,则将和合并成一个集合,表示建立新的朋友关系。
最后,我们统计并查集中集合的数量,即为可以执行操作的最大次数。
100 分做法
一个 个点的边双连通分量,最多可以连$$\binom{s}{2} = \frac{s*(s-1)}{2}$$ 条边,对于题目给出的森林,用并查集维护连通块,连接给定的每组($$a$$,$$b$$),合并($$a$$,$$b$$)所在的两个连通块,同时统计每个连通块的边数,最大边数-现有边数=当前可以连的边数。
- 1
信息
- ID
- 118
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者