一、题目

　　

二、题目链接

　　

三、题意

　　给定一个$N$和$M$。$N$表示有$N$个点，$M$表示，在一个$N$个点组成的无向完全图中，接下来的$M$条无向边不存在。

　　问你在这个图中有多少个连通分量，并且从小到大输出每个连通分量的顶点个数。

四、思路

　　求无向图的连通分量个数，只需要跑一边bfs就OK了。其实dfs也可以，只是太多的“函数压栈现场保护”浪费一丢丢时间而已，慢一点点，影响其实并不大。

　　要注意的是，无论跑bfs还是dfs，不能枚举边，因为这题的边数太多了，会超时。只能枚举点，枚举所有未访问的点。

　　然后，在跑bfs的过程中，统计这次bfs访问的点的个数，返回就OK了。枚举每一个点，如果是未访问的，就跑一遍bfs，记录这次bfs访问的点的个数，问题就解决了。

五、源代码

　　

#pragma GCC optimize(2)#pragma comment(linker, "/STACK:102400000, 102400000")#include
     
      using namespace std;typedef long long LL;const int MAXN = 2e5 + 10;template 
      
        inline void read(T &x) {    int t;    bool flag = false;    while((t = getchar()) != '-' && (t < '0' || t > '9')) ;    if(t == '-') flag = true, t = getchar(); x = t - '0';    while((t = getchar()) >= '0' && t <= '9') x = x * 10 + t - '0';    if(flag) x = -x;}int n, m;unordered_set
       
         g[MAXN], invis;vector
        
          ans, tmp;queue
         
           que;int bfs(int s) {    int res = 1;    while(!que.empty())que.pop();    que.push(s);    invis.erase(s);    while(!que.empty()) {        int t = que.front();        que.pop();        tmp.clear();        for(auto x : invis) {
   //注意不要边迭代、边移除。            if(g[t].count(x))continue;            else {                que.push(x);                tmp.push_back(x);                res++;            }        }        for(auto x : tmp)invis.erase(x);    }    return res;}void init() {    invis.clear();    for(int i = 1; i <= n; ++i)invis.insert(i);    for(int i = 0; i < MAXN; ++i)g[i].clear();    ans.clear();}int main() {#ifndef ONLINE_JUDGE    freopen("Einput.txt", "r", stdin);#endif // ONLINE_JUDGE    int a, b;    scanf("%d%d", &n, &m);    init();    for(int i = 0; i < m; ++i) {        read(a), read(b);        g[a].insert(b);        g[b].insert(a);    }    for(int i = 1; i <= n && invis.size() > 0; ++i) {        if(invis.count(i))ans.push_back(bfs(i));    }    sort(ans.begin(), ans.end());    printf("%d\n", ans.size());    for(auto x : ans)printf("%d ", x);    return 0;}