Connected components in complement graph, C++ (gcc)

Connected components in complement graph

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair

struct DSU{
    vector<int> p, sz;
    int n;
    
    DSU(int x) : n(x){
        p.resize(n+1);
        sz.resize(n+1, 1);
        for(int j = 1; j <= n; j++) p[j] = j;
    }
    
    void merge(int u, int v){
        u = par(u);
        v = par(v);
        if(u == v) return;
        if(sz[u] > sz[v]) swap(u, v);
        sz[v] += sz[u];
        p[u] = v;
    }
    
    int par(int u){
        return (u == p[u])? u : (p[u] = par(p[u]));
    }
};

const int N = 5e5 + 5;
vector<int> g[N];

int main(){
    
    
    int n, m;
    scanf("%d %d",&n ,&m);
    vector<int> deg(n+1, 0);
    set<pii> edges;
    
    for(int j = 0; j < m; j++){
        int u, v;
        scanf("%d %d",&u ,&v);
        if(u > v) swap(u, v);
        edges.insert({u, v});
        
        g[u].pb(v);
        g[v].pb(u);
        deg[u] ++, deg[v] ++;
    }
    int mn = 1e9, ind = 0;
    for(int j = 1; j <= n; j++)
        if(deg[j] < mn) mn = deg[j], ind = j;
    
    DSU dsu(n);
    vector<int> other, vis(n+1, 0);
    for(auto i : g[ind])
        other.pb(i), vis[i] = 1;
    for(int j = 1; j <= n; j++)
        if(j != ind && !vis[j])
            dsu.merge(j, ind);
    
    sort(other.begin(), other.end());
    
    int x = other.size();
    for(int j = 0; j < x; j++){
        for(int i = j+1; i < x; i++)
            if(edges.find({other[j], other[i]}) == edges.end()) dsu.merge(other[j], other[i]);
    }
    vector<int> merge_it;
    for(auto i : other){
        int edges_to_ind = 0;
        for(auto j : g[i])
            if(dsu.par(j) == dsu.par(ind)) edges_to_ind ++;
        // cout << edges_to_ind << " " << i << endl;
        if(edges_to_ind != (n - (int)g[ind].size())) merge_it.pb(i);
    }
    for(auto i : merge_it) dsu.merge(ind, i);
    
    set<int> comps;
    for(int j = 1; j <= n; j++) comps.insert(dsu.par(j));
    vector<pii> v;
    for(int j = 1; j <= n; j++) v.pb({dsu.par(j), j});
    sort(v.begin(), v.end());
    
    printf("%d\n",(int)comps.size());
    vector<int> sz;
    for(int j = 0; j < n; j++){
        int cur = v[j].F, cnt = 0;
        vector<int> x;
        while(j < n && cur == v[j].F) x.pb(v[j].S), j++, cnt ++;
        j--;
        sz.pb(cnt);
        // printf("%d ", cnt);
        // for(auto i : x) printf("%d ",i); printf("\n");
    }
    sort(sz.begin(), sz.end());
    for(auto i : sz) printf("%d ", i);
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development