2020-2021:teams:hotpot:2020nowcoder3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:2020nowcoder3 [2020/07/24 14:42] lotk |
2020-2021:teams:hotpot:2020nowcoder3 [2020/07/24 15:00] (当前版本) lotk |
||
|---|---|---|---|
| 行 77: | 行 77: | ||
| ===题解=== | ===题解=== | ||
| - | ====G - ==== | + | ====G - Operating on a Graph==== |
| - | ===solved by === | + | ===solved by lxh，gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给出一些点和一些边，每次选定一个点，使这个点所代表的集合通过延伸出去的边覆盖周围的集合（被覆盖的集合无法再扩展） | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 点数 $ 2 \le n \le 800005 $ | ||
| + | 边数 $ 1 \le m \le 800005 $ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 我们可以发现，每次扩展中，已经用于扩展的点就不会再次使用了。利用这个性质，我们可以通过手写链表对每个集合含有哪些点进行处理，每次将链表弹空并通过枚举边和并查集判断加入新点即可。 | ||
| ====H - ==== | ====H - ==== | ||
2020-2021/teams/hotpot/2020nowcoder3.1595572957.txt.gz · 最后更改: 2020/07/24 14:42 由 lotk
