Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Zahra_matrix
Matrix spiral print
MapTel2
cppPyGuessTheNum2
without HLD range Quey can be handled by just using segment tree on the FLATTENED TREE (euler tour)
ახარისხება~ფინალური
D. Traveling Graph
Tubee c++
vector fr
Elevator 3