并查集+dfs
先开始想和不相连的点用并查集连起来,最后看每个连通块有多少个点就行了,但是这样是O(n*n)的,然而我并没有想到补图
其实就是求补图有多少连通块,因为补图中两个点有边,那么这两个点必须在一栋大楼里,因为他们之间没有联系,然后这样就有了许多连通块,不同的连通块可以不相连,因为不同的连通块之间没有边,也就是不同的连通块的点之间都有联系,然后我们只要求出这样的连通块的数量和大小。
但是补图太稠密,不能直接求,然后我们就要用奇技淫巧来优化,我们用并查集维护每个点,用并查集维护下一个没有用过的点是哪个,然后我们dfs,用并查集查询下一个没有访问过的点,然后判断当前的点和那个点在原图中是否相连,相连的话说明这两个点在补图中没有边,没有必要访问,因为两个点或许不在一个连通块内,而且两个点在补图中不相连,自然不会访问。如果一个点已经被访问,那么自然不会再次访问,于是,每个点访问一次,边访问一次,复杂度O(n+m)
#include<bits/stdc++.h>
using namespace std;
const int N = ;
int n, m, cnt;
int fa[N], ans[N];
vector<int> G[N];
inline int read()
{
int x = , f = ; char c = getchar();
while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }
while(c >= '' && c <= '') { x = x * + c - ''; c = getchar(); }
return x * f;
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void dfs(int u)
{
++ans[cnt];
fa[u] = find(u + );
for(int i = find(); i <= n; i = find(i + ))
{
bool flag = true;
for(int j = ; j < G[u].size(); ++j)
{
int v = G[u][j];
if(v == i)
{
flag = false;
break;
}
}
if(flag) dfs(i);
}
}
int main()
{
n = read();
m = read();
for(int i = ; i <= m; ++i)
{
int u = read(), v = read();
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = ; i <= n + ; ++i) fa[i] = i;
for(int i = ; i <= n; ++i) if(fa[i] == i)
{
++cnt;
dfs(i);
}
printf("%d\n", cnt);
sort(ans + , ans + cnt + );
for(int i = ; i <= cnt; ++i) printf("%d ", ans[i]);
return ;
}