qwq 从另一个方向考虑会有新的想法

懵逼的 题目

qwq

扯淡的 题解

如果…我…不二分的话…我是不是可以把没有联系方式的人之间连边…然后…难道就是…连通块的个数?

复杂度是不是炸了

如果我稍微…优化一下…

…1h passed

无果, 遂翻题解…链表优化$bfs$…Emmmmmmm? 这是个啥玩意…

仔细想了一下…Emmmmmmm! 我们只要保证一个点只会被遍历一遍不就行了qwq

那么, 我们用一个链表, 存下所有的点, 代表还未遍历过的点

每次:

  • 从链表头取出一个元素, 把他删掉, 加到队列里
  • 开始$bfs$, 每次从队首取出一个元素. 遍历链表, 如果链表中当前的元素与当前节点没有边相连, 就把这个点从链表中删除, 并加入队列, 当前联通块的大小$+1$

这样就保证了所有的点只会被遍历一次, 是不是很妙?

至于怎么确定一个点是否和当前点有边相连, 直接用set<int>[]会$TLE$…所以我们可以搞一个vis[], 记录与当前点相连的点即可

沙茶的 代码

/**************************************************************
    Problem: 1098
    User: Cansult
    Language: C++
    Result: Accepted
    Time:8760 ms
    Memory:52372 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#include <algorithm>
#include <set>
#include <list>
#include <queue>
#include <vector>
#define MAXN (100000 + 5)
#define MAXM (2000000 + 5)
using namespace std;
struct edg
{
    int from, to, next;
}b[MAXM << 1];
vector<int> ans;
set<int> edg[MAXN];
int n, m, g[MAXN], cntb;
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to;
    g[from] = cntb;
}
void bfs()
{
    list<int> sh;
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= n; i++)
        sh.push_back(i);
    while (!sh.empty())
    {
        int s = *sh.begin();
        sh.pop_front();
        queue<int> q;
        q.push(s);
        int cnt = 1;
        while (!q.empty())
        {
            int dq = q.front();
            q.pop();
            for (int i = g[dq]; i; i = b[i].next)
                vis[b[i].to] = true;
            for (list<int>::iterator i = sh.begin(), j; i != sh.end();)
                if (!vis[*i])
                {
                    q.push(*i);
                    ++cnt;
                    j = i;
                    ++i;
                    sh.erase(j);
                }
                else
                    ++i;
            for (int i = g[dq]; i; i = b[i].next)
                vis[b[i].to] = false;
        }
        ans.push_back(cnt);
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++)
        printf("%d ", ans[i]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, srx, sry; i <= m; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    bfs();
    return 0;
}

By 沙茶 Cansult