CF920E 题解

考虑直接暴力 dfs。设搜到点 $u$，把 $u$ 打上 tag，然后我们枚举 $v$ 使得 $v$ 没被打上 tag 且边 $(u, v)$ 不存在，搜点 $v$ 即可。复杂度 $O(n^2)$。 发现瓶颈在于寻找没被打上 tag 的点。考虑使用链表，维护还没被打上 tag 的点，搜到 $u$ 时将 $u$ 从链表中删除，再遍历一遍链表即可。 实现时可以用并查集模拟链表。时间复杂度 $O((n + m) \log n)$。 [code](https://codeforces.com/problemset/submission/920/213103244)