Connected Components? CodeForces - 920E (bfs) - JavaScript

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

大意:给定无向图, 求补图的连通块数

bfs模拟即可, 用了map存图, set维护未划分的点集, 复杂度$O(nlog^2n)$, 用链表的话可以$O(n)$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_backusing namespace std;const int N = 4e5+, INF = 0x3f3f3f3f;
int n, m;
map<int,int> a[N];
set<int> s;
int sz[N];int main() {
scanf("%d%d", &n, &m);
REP(i,,m) {
int u, v;
scanf("%d%d", &u, &v);
a[u][v]=a[v][u]=;
}
REP(i,,n) s.insert(i);
REP(i,,n) if (s.count(i)) {
queue<int> q;
q.push(i);
int cnt = ;
while (!q.empty()) {
int i=q.front();q.pop();
vector<int> tmp;
for (int j:s) if (!a[i][j]) {
++cnt, q.push(j), tmp.pb(j);
}
for (int j:tmp) s.erase(j);
}
sz[++*sz] = cnt;
}
printf("%d\n", *sz);
sort(sz+,sz++*sz);
REP(i,,*sz) printf("%d ",sz[i]);
puts("");
}