CF920E 题解

EuphoricStar · 2023-07-10 19:16:08 · 题解

考虑直接暴力 dfs。设搜到点 u，把 u 打上 tag，然后我们枚举 v 使得 v 没被打上 tag 且边 (u, v) 不存在，搜点 v 即可。复杂度 O(n^2)。

发现瓶颈在于寻找没被打上 tag 的点。考虑使用链表，维护还没被打上 tag 的点，搜到 u 时将 u 从链表中删除，再遍历一遍链表即可。

实现时可以用并查集模拟链表。时间复杂度 O((n + m) \log n)。

code