CF920E Connected Components? 题解

· · 题解

一道线段树优化建图好题（大雾

扣掉一些边看起来不好做，我们直接大力加上存在的边，然后跑连通块。对于一个点，如果他被扣掉了 k 个邻居，那么没扣掉的那些形成了至多 k+1 个连续段，可以用线段树优化建图向每个连续段各用 \log 的代价连边。

由于总共扣掉了 m 条边，所以总共连边的次数是 O(m) 的，建图复杂度为 m\log m，产生 O(n+m) 个点、O(n+m) 条边的有向图。

注意到线段树优化建图建的是有向图，如果直接建无向图就会让所有点都在一个连通块。所以按照有向的线段树优化建图做法，如下：

（图为 2 向 3,4 连边）（由于是点向区间连边，只需要一棵线段树即可）

注意到，在 2 向 3,4 连边时，3,4 也会向 2 连边，故连通块一定形成强连通分量，也不会产生直接连无向图的问题。于是最后对新图跑一下强连通分量即可。

#include <bits/stdc++.h>
using namespace std;
vector<int> a[200010], e[600010];
int n, m, tot, rt;
struct node{int lson, rson;} t[600010];
#define mid (l + r) / 2
void build(int &now, int l = 1, int r = n) {
    if (l == r) {now = l + n; return;}
    now = ++tot;
    build(t[now].lson, l, mid), build(t[now].rson, mid + 1, r);
    e[now].push_back(t[now].lson), e[now].push_back(t[now].rson);
}
void add(int now, int ql, int qr, int x, int l = 1, int r = n) {
    if (ql <= l && qr >= r) {e[x].push_back(now); return;}
    if (ql <= mid) add(t[now].lson, ql, qr, x, l, mid);
    if (qr > mid) add(t[now].rson, ql, qr, x, mid + 1, r);
}
int dfn[600010], low[600010], cnt;
int st[600010], top, col[600010], colcnt, sz[600010];
bool in[600010];
void dfs(int now) {
    low[now] = dfn[now] = ++cnt;
    st[++top] = now, in[now] = 1;
    for (int v : e[now]) {
        if (!dfn[v]) dfs(v), low[now] = min(low[now], low[v]);
        else if (in[v]) low[now] = min(low[now], dfn[v]);
    }
    if (low[now] == dfn[now]) {
        colcnt++;
        while (st[top] != now)
            col[st[top]] = colcnt, in[st[top]] = 0, top--;
        col[st[top]] = colcnt, in[st[top]] = 0, top--;
    }
}
signed main() {
    scanf("%d%d", &n, &m), tot = n * 2;
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y), a[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        e[i + n].push_back(i);
    build(rt, 1, n);
    for (int i = 1; i <= n; i++) {
        a[i].push_back(0), a[i].push_back(n + 1);
        sort(a[i].begin(), a[i].end());
        for (int j = 1; j < a[i].size(); j++) {
            if (a[i][j - 1] + 1 == a[i][j]) continue;
            add(rt, a[i][j - 1] + 1, a[i][j] - 1, i);
        }
    }
    for (int i = 1; i <= tot; i++)
        if (!dfn[i]) dfs(i);
    for (int i = 1; i <= n; i++)
        sz[col[i]]++;
    sort(sz + 1, sz + colcnt + 1);
    vector<int> ans;
    for (int i = 1; i <= colcnt; i++)
        if (sz[i]) ans.push_back(sz[i]);
    printf("%d\n", (int)ans.size());
    for (int x : ans) printf("%d ", x);
    puts("");
    return 0;
}