백준 1741번 반 나누기

문제 링크 참고 문헌

풀이 보고 풀었다.

나이브하게 생각하면 연결 안된 정점 쌍을 dsu로 묶어주면 된다. 이걸 빠르게 해야한다.

연견된 간선이 가장 작은 정점을을 $a$라고 하자. $a$와 연결된 간선은 최대 $\frac{M}{N}$개이다. $a$와 연결된 정점 집합을 $A$, 아닌 집합을 $B$라고 하자. $A$의 크기는 최대 $\frac{M}{N}$이다.

$B$와 $a$를 dsu로 묶어주자. 이제 이들 끼리는 서로 확인할 필요가 없다. $A$ 집합와 모든 정점에 대해 나이브하게 처리한다. 그러면 $N \cdot \frac{M}{N}$개의 쌍을 봐야해서 $O(M \cdot \log N)$에 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

struct DSU {
    int N;
    vector<int> root;
    DSU(int _N) : N(_N) {
        root.resize(N+1);
        iota(root.begin(), root.end(), 0);
    }

    int find(int x)
    {
        if(root[x] == x) return x;
        return root[x] = find(root[x]);
    }

    void merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        root[y] = x;
    }
};

const int MAXN = 101010;

int n, m, cnt[MAXN];
vector<int> g[MAXN];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    DSU dsu(n);
    int mn = 1e9;
    int mni = -1;
    for(int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
        if(g[i].size() < mn) {
            mn = g[i].size();
            mni = i;
        }
    }
    vector<int> A = g[mni];
    for(int i = 1; i <= n; i++) {
        if(!binary_search(A.begin(), A.end(), i)) dsu.merge(mni, i);
    }
    for(int u = 1; u <= n; u++) {
        for(int j = 0; j < A.size(); j++) {
            int v = A[j];
            if(!binary_search(g[u].begin(), g[u].end(), v)) dsu.merge(u, v);
        }
    }
    for(int i = 1; i <= n; i++) {
        cnt[dsu.find(i)]++;
    }
    vector<int> v;
    for(int i = 1; i <= n; i++) {
        if(i == dsu.find(i)) v.push_back(cnt[dsu.find(i)]);
    }
    sort(v.begin(), v.end());
    cout << v.size() << "\n";
    for(auto i : v) cout << i << " ";
}