CF 920E Connected Components?

题目描述

https://codeforces.com/problemset/problem/920/E

简要题意：给定一个 $n$ 个点 $m$ 条边简单无向图，求该图的补图的连通块个数

$n,m\le 2\times 10^5$

Solution

我们考虑每次从一个没有到过的点开始 $dfs$，$dfs$ 的次数即为连通块的个数

那么我们全局维护一个当前没有到过的点的集合 $S$，与一个点连通的点即为 $S$ 中与其没有边的点，我们遍历 $S$ 中所有点，保留有边的点，然后其他点全部删除，这样每次暴力做的时间复杂度为 $O(n+m)$

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 200010
using namespace std;

int n, m;

vector<int> G[maxn]; int du[maxn];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y) { fa[find(x)] = find(y); }

bool vis[maxn], use[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    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);
        ++du[x]; ++du[y];
    } int p = min_element(du + 1, du + n + 1) - du;
    init_fa(n); vector<int> vec; fill(vis + 1, vis + n + 1, 1);
    for (auto v : G[p]) vis[v] = 0; 
    for (int u = 1; u <= n; ++u) 
        if (!vis[u]) vec.push_back(u);
        else merge(u, p);
    for (int u = 1; u <= n; ++u) {
        if (vis[u]) continue;
        for (auto v : G[u]) use[v] = 1;
        for (int v = 1; v <= n; ++v) if (!use[v]) merge(u, v); 
        for (auto v : G[u]) use[v] = 0; 
    } vector<int> ans, cnt(n + 1); 
    for (int i = 1; i <= n; ++i) ++cnt[find(i)], find(i) == i && (ans.push_back(i), 0);
    cout << ans.size() << "\n"; sort(ans.begin(), ans.end(), [&](const int &u, const int &v) { return cnt[u] < cnt[v]; }); 
    for (auto t : ans) cout << cnt[t] << " "; cout << "\n";
    return 0; 
}