Codeforces 920E(BFS+链表优化)

Codeforces 920E
题意:给你一个无向图,求它补图的连通分量个数以及所有连通分量的大小,升序输出。

这题也就只能 BFS 暴力了,最开始将所有点放进一个数组,然后每次从里面拿一个出来 BFS 扩展,然后每一层扩展到的点实际上是不可达的,要把没有扩展到的点加进队列,并且在数组中删除。这样找出来就是一个联通分量了。但是数组要支持删除很慢,我们就用链表来做。

知识点:链表让数组支持$O(1)$删除,BFS取没有扩展的点加入队列的思想很好。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;

const int MAXN = 200000 + 5;

int n, m, l[MAXN], r[MAXN], vis[MAXN];
vector<int> G[MAXN], ans;
queue<int> q;

inline void ins(int x, int y) {G[x].push_back(y), G[y].push_back(x);}
inline void del(int x) {r[l[x]] = r[x], l[r[x]] = l[x];}

void bfs(int s) {
    int sz = 0;
    q.push(s), vis[s] = s;
    while (!q.empty()) {
        sz++;
        int u = q.front(); q.pop();
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            if (vis[v] != u) vis[v] = u;
        }
        for (int i = r[0]; i != -1; i = r[i]) if (i != s && vis[i] != u) q.push(i), del(i);
    }
    ans.push_back(sz);
}

void clean() {
    ms(vis, 0);
}
int solve() {
    clean();
    for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y);

    for (int i = 1; i <= n; i++) l[i] = i - 1, r[i - 1] = i;
    l[0] = -1, r[n] = -1;

    for (int i = r[0]; i != -1; i = r[i]) bfs(i), del(i);

    sort(ans.begin(), ans.end());

    printf("%d\n", (int)ans.size());
    for (int i = 0; i < (int)ans.size(); i++) printf("%d ", ans[i]);

    return 0; 
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}
------ 本文结束 ------