实际上对于任意的连通图都一定有解，我们只需要取原图的一棵生成树。
对树进行 DFS，如果当前子树的深度达到了 $\lceil\sqrt N\rceil$ 或者是整棵树的根，就将当前结点加入集合，并将子树删除。除了最后一次，其余每一次至少删掉 $\lceil\sqrt N\rceil$ 个点，所以总点数不超过 $\lceil \sqrt N\rceil$。
时间复杂度 $O(N+M)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #128 for Problem #6634. Central Subset
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-12 23:27:24
Last updated: 2025-12-12 23:27:33
题解
Comments
No comments yet.