实际上对于任意的连通图都一定有解，我们只需要取原图的一棵生成树。

对树进行 DFS，如果当前子树的深度达到了 $\lceil\sqrt N\rceil$ 或者是整棵树的根，就将当前结点加入集合，并将子树删除。除了最后一次，其余每一次至少删掉 $\lceil\sqrt N\rceil$ 个点，所以总点数不超过 $\lceil \sqrt N\rceil$。

时间复杂度 $O(N+M)$。