题意

给定一个图，我们需要遍历所有顶点。图可能不是完全连通的，且边数可能较少。目标是使用一种改进的深度优先搜索（DFS）来高效地遍历图，并处理未访问顶点的集合。

思路

我们维护一个未访问顶点的集合 $S$。在 DFS 过程中，每当进入一个顶点时，就将其从 $S$ 中删除。关键技巧是：在 DFS 中，我们使用集合的 upper_bound 函数来迭代未访问的顶点。这样，整体迭代次数不会超过 $O(m + n)$，因为：

• 每次跳过未访问顶点意味着当前顶点与该顶点之间没有边，这样的跳过最多发生 $2m$ 次；
• 每次不跳过的迭代都会减少未访问顶点的数量。

算法步骤

1. 初始化一个数据结构（如 C++ 的 std::set<int>）来存储所有未访问的顶点。
2. 从任意一个顶点开始进行 DFS：
   • 进入当前顶点时，将其从未访问集合中删除。
   • 使用 upper_bound 函数在未访问集合中查找下一个可能访问的顶点。
   • 如果找到的顶点与当前顶点之间有边，则递归访问该顶点；否则跳过。
3. 重复步骤 2，直到所有顶点都被访问。

复杂度分析

• 时间复杂度：$O(m + n)$，其中 $n$ 是顶点数，$m$ 是边数。因为每次跳过未访问顶点最多 $2m$ 次，且每次不跳过的迭代都会减少未访问顶点数。
• 空间复杂度：$O(n)$，用于存储未访问顶点集合和邻接表。

代码说明

• 使用 std::set<int> 来存储未访问顶点，支持插入、删除和 upper_bound 操作。
• 邻接表可以用类似的数据结构存储，以便快速判断两个顶点之间是否有边。
• DFS 实现中，每次进入顶点时从集合中删除该顶点，并利用 upper_bound 在未访问顶点中查找下一个可能访问的顶点。

#include <cstdio>
#include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;

unordered_set <int>mp[200010];

queue <int>vec;

int n,m,cnt;

int ans[200010];

bool vis[200010];

void bfs(int x,int cnt)
{
  queue <int>q;
  q.push(x);
  while(!q.empty())
  {
    int x=q.front(),nowsize=vec.size();
    q.pop();
    for(int i=1;i<=nowsize;i++)
    {
      int now=vec.front();
      vec.pop();
      if(vis[now]) continue ;
      if(mp[x].find(now)!=mp[x].end()||mp[now].find(x)!=mp[now].end()) vec.push(now);
      else ans[cnt]++,q.push(now),vis[now]=1;
    }
  }
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int a,b;
    scanf("%d%d",&a,&b);
    mp[a].insert(b);
  }
  for(int i=1;i<=n;i++) vec.push(i);
  for(int i=1;i<=n;i++)
  {
    if(!vis[i])
    {
      vis[i]=1;
      bfs(i,++cnt);
    }
  }
  sort(ans+1,ans+cnt+1);
  printf("%d\n",cnt);
  for(int i=1;i<=cnt;i++) printf("%d ",ans[i]+1);
}