题目大意
题目链接
求补图连通块的个数以及各个连通块的大小。
分析
参照了ww140142的做法。
每次枚举一个未在连通块的点，然后从它开始宽搜出它所在的连通块；
具体是枚举它的所有原图的边，标记起来，枚举边之后再枚举所有的点，将未标记的点加入该连通块，并加入队列继续宽搜；
为了节约无用的枚举，我们还需要对所有点构建链表，将已经在某个块内的点删除；
这个算法的复杂度是O(n+m)的；
原因是每一个点仅进行了一次宽搜的拓展；
并且在每次拓展中，枚举边表总复杂度是O(m)；
而之后的枚举剩下的点，我们将点分为两部分：已标记的点的复杂度计在O(m)之内，而未标记的点将会被加入队列，这个过程对每个点也仅有一次；
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, cnt, u, v, lst[N], nxt[N], vis[N], ans[N];
vector<int>ve[N]; queue<int>q;
inline void del(int x){ nxt[lst[x]] = nxt[x]; lst[nxt[x]] = lst[x]; }
void solve(){
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
scanf("%d%d", &u, &v), ve[u].push_back(v), ve[v].push_back(u);
for (int i = 1; i < n; ++i) lst[i + 1] = i, nxt[i] = i + 1;
nxt[0] = 1;
for (int i = 1; i <= n; ++i){
if (vis[i]) continue;
ans[++cnt] = vis[i] = 1; q.push(i);del(i);
while(!q.empty()){
int u = q.front();q.pop();
for (int j = 0; j < ve[u].size(); ++j) if (!vis[ve[u][j]]) vis[ve[u][j]] = 1;
for (int j = nxt[0]; j; j = nxt[j])
if (!vis[j]) {vis[j] = 1;++ans[cnt];del(j);q.push(j);}
else vis[j] = 0;
}
}
sort(ans + 1, ans + 1 + cnt);
printf("%d\n", cnt);
for (int i = 1; i < cnt; ++i) printf("%d ", ans[i]); printf("%d\n", ans[cnt]);
}
int main(){solve();return 0;}
|
后继
相关题目
CodeForces - 920E
CodeForces-1242B
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。 --mingfuyan
千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。