一道线段树优化建图好题（大雾
扣掉一些边看起来不好做，我们直接大力加上存在的边，然后跑连通块。对于一个点，如果他被扣掉了 \(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;
}