fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std ;
  4.  
  5. #define ll long long
  6. #define sz(x) x.size()
  7. // bitmasks
  8. // Number of leading zeroes: __builtin_clz(x)
  9. // Number of trailing zeroes : __builtin_ctz(x)
  10. // Number of 1-bits: __builtin_popcount(x);
  11. // last one : __lg()
  12. template<typename T = ll, ll Base = 1>
  13. struct DSU {
  14.     ll n;
  15.     vector<T> parent, Gsize, nxt, tail, pos, roots;
  16.  
  17.     DSU(ll MaxNodes) {
  18.         n = MaxNodes + 1;
  19.         parent = Gsize = roots = tail = pos = nxt = vector<T>(MaxNodes + Base);
  20.         for (ll i = Base; i < MaxNodes + Base; i++) {
  21.             parent[i] = roots[i] = pos[i] = tail[i] = i;
  22.             nxt[i] = -1, Gsize[i] = 1;
  23.         }
  24.     }
  25.  
  26.     T find_leader(ll node) {
  27.         return parent[node] = (parent[node] == node ? node : find_leader(parent[node]));
  28.     }
  29.  
  30.     bool is_same_sets(ll u, ll v) {
  31.         return find_leader(u) == find_leader(v);
  32.     }
  33.  
  34.     bool union_sets(ll u, ll v) {
  35.         ll leader_u = find_leader(u), leader_v = find_leader(v);
  36.         if (leader_u == leader_v) return 0;
  37.         // make leader_u is the leader with the larger component
  38.         if (Gsize[leader_u] < Gsize[leader_v])
  39.             swap(leader_u, leader_v);
  40.         ll p = pos[leader_v];
  41.         Gsize[leader_u] += Gsize[leader_v];
  42.         parent[leader_v] = leader_u;
  43.         roots[p] = roots.back();
  44.         pos[roots[p]] = p;
  45.         roots.pop_back();
  46.         nxt[tail[leader_u]] = leader_v;
  47.         tail[leader_u] = tail[leader_v];
  48.         return 1;
  49.     }
  50.  
  51.     void print() {
  52.         for (ll root = Base; root < sz(roots); root++) {
  53.             for (ll u = roots[root]; ~u; u = nxt[u])
  54.                 cout << u << " \n"[!~nxt[u]];
  55.         }
  56.     }
  57.  
  58.     vector<vector<ll> > get_components() {
  59.         vector<vector<ll> > components;
  60.         for (ll root = Base; root < sz(roots); root++) {
  61.             vector<ll> component;
  62.             for (ll u = roots[root]; ~u; u = nxt[u])
  63.                 component.push_back(u);
  64.             components.push_back(component);
  65.         }
  66.         return components;
  67.     }
  68.  
  69.     ll get_size(ll u) {
  70.         return Gsize[find_leader(u)];
  71.     }
  72.  
  73.     ll get_components_number() {
  74.         return sz(roots) - Base;
  75.     }
  76.  
  77.     ll has_supervisor(ll b) {
  78.         return parent[b] != b;
  79.     }
  80.  
  81.     void clear() {
  82.         parent = Gsize = roots = tail = pos = nxt = vector<T>(n + Base);
  83.         for (ll i = Base; i < n + Base; ++i) {
  84.             parent[i] = roots[i] = pos[i] = tail[i] = i;
  85.             nxt[i] = -1, Gsize[i] = 1;
  86.         }
  87.     }
  88. };
  89.  
  90. struct edge {
  91.     ll n, u, v, w;
  92. };
  93.  
  94. const ll MOD = 1e9;
  95.  
  96. #define u first
  97. #define v second
  98.  
  99. void solve() {
  100.     ll n, m;
  101.     cin >> n >> m;
  102.     vector<pair<ll,ll> > edges(m + 1);
  103.  
  104.     for (ll i = 1; i <= m; i++) {
  105.         auto &e = edges[i];
  106.         cin >> e.u >> e.v;
  107.     }
  108.  
  109.     vector<vector<ll> > pref_leader(m + 1, vector<ll>(n + 1)), suff_leader(m + 1, vector<ll>(n + 1));
  110.  
  111.     DSU<ll> dsu(n);
  112.  
  113.     for (ll i = 1; i <= m; i++) {
  114.         dsu.union_sets(edges[i].u, edges[i].v);
  115.         for (ll j = 1; j <= n; j++) {
  116.             pref_leader[i][j] = dsu.find_leader(j);
  117.         }
  118.     }
  119.  
  120.     DSU<ll> dsu2(n);
  121.  
  122.     for (ll i = m; i >= 1; i--) {
  123.         dsu2.union_sets(edges[i].u, edges[i].v);
  124.         for (ll j = 1; j <= n; j++) {
  125.             suff_leader[i][j] = dsu2.find_leader(j);
  126.         }
  127.     }
  128.  
  129.     ll q;
  130.     cin >> q;
  131.     while (q--) {
  132.         ll l, r;
  133.         cin >> l >> r;
  134.  
  135.         DSU<ll> qd(n);
  136.  
  137.         if (l - 1 >= 1)
  138.             qd.parent = pref_leader[l - 1];
  139.  
  140.         for (ll i = 1; i <= n; i++) {
  141.             if (r + 1 > m)break;
  142.             qd.union_sets(i, suff_leader[r + 1][i]);
  143.         }
  144.  
  145.         cout << qd.get_components_number() << endl;
  146.     }
  147. }
  148.  
  149. int main() {
  150.     ios::sync_with_stdio(false);
  151.     cin.tie(nullptr);
  152.     // ll t;
  153.     // cin >> t;
  154.     // while (t--)
  155.     solve();
  156. }
  157.  
  158. /*
  159. If you have number of nodes connected with edges ( 1 ... m ) 
  160. There is a queries asking if you removed edges from ( l .. r )
  161. What is the number of connected components for each query ? 
  162.  
  163. - Create pre computed pref_leader and suff_leader arraies
  164. - on creating new edge get the parent of all the nodes after connecting this edge
  165.     for edge number x 
  166.     for i = 1 -> n  pref_leader[x][i] = dsu.find_leader(i);
  167. - connect the graph in reverse edges , compute the suff_leader
  168. - for L and R query connect the nodes to their parents at L-1 and R+1 
  169. - Count the components.
  170. */
  171.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/agxVdH
If you have number of nodes connected with edges ( 1 ... m )
There is a queries asking if you removed edges from ( l .. r )
What is the number of connected components for each query ?

- Create pre computed pref_leader and suff_leader arraies
- on creating new edge get the parent of all the nodes after connecting this edge
for edge number x
for i = 1 -> n pref_leader[x][i] = dsu.find_leader(i);
- connect the graph in reverse edges , compute the suff_leader
- for L and R query connect the nodes to their parents at L-1 and R+1
- Count the components.
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!