【Educational Codeforces Round 37 E】Connected Components?

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

bfs.
用一个链表来记录哪些点已经确定在某一个联通快里了。
一开始每个点都能用。
然后从第一个点开始进行bfs.
然后对于它的所有连接着的点(输入的图的补图
看看它是不是之前进行过bfs,如果是的话。就跳过。(可以用链表直接跳过。即沿着链表枚举它的出度。
否则。把这个点从链表中删掉。然后把这个点加入队列。继续bfs即可。
这样已经确定联通了的点之间不会再访问。
链表加速了寻找某个点的出度的过程。
且由于当n很大的时候。m只有200000
因此可以很快地进入某个点的bfs.所以链表的删除速度会很快。

【代码】

#include<bits/stdc++.h>
using namespace std;const int N = 2e5;int n,m;
vector<int> g[N+10];
int nex[N+10],bef[N+10],ban[N+10];
bool _deleted[N+10];
queue<int> dl;
vector<int> ans;void _delete(int x){
_deleted[x] = 1;
int y = bef[x],z = nex[x];
nex[y] = z;
bef[z] = y;
}void bfs(int x){
ans.push_back(1);
_delete(x);
dl.push(x);
while (!dl.empty()){
int x = dl.front();
dl.pop();
for (int y:g[x]) ban[y] = 1; for (int i = nex[0];i!=n+1;i=nex[i]){
if (ban[i]) continue;
_delete(i);
dl.push(i);
ans.back()++;
} for (int y:g[x]) ban[y] = 0;
}
}int main()
{
cin >> n >> m;
for (int i = 1;i <= m;i++){
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 0;i <= n+1;i++)
nex[i] = i+1,bef[i] = i-1;
for (int i = 1;i != n+1;i=nex[i]){
if (_deleted[i]) continue;
bfs(i);
}
cout<<(int)ans.size()<<endl;
sort(ans.begin(),ans.end());
for (int x:ans)
cout<<x<<' ';
return 0;
}