fork(16) download
copy 
  1. /**
  2.  * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
  3.  * Date: 2013.09.08
  4.  */
  5.  
  6. #include <cstdio>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <map>
  11.  
  12. using namespace std;
  13.  
  14. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  15. #define forit(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
  16. #define pb push_back
  17. #define mp make_pair
  18. #define sz(a) (int)(a).size()
  19.  
  20. typedef vector <int> vi;
  21. typedef pair <int, int> pii;
  22.  
  23. const int N = (int)3e5;
  24.  
  25. struct edge
  26. {
  27.   int a, b, l, r;
  28. };
  29. typedef vector <edge> List;
  30.  
  31. int cnt[N + 1], ans[N], u[N], color[N], deg[N];
  32. vi g[N];
  33.  
  34. void add( int a, int b )
  35. {
  36.   g[a].pb(b), g[b].pb(a);
  37. }
  38.  
  39. void dfs( int v, int value )
  40. {
  41.   u[v] = 1, color[v] = value;
  42.   forn(i, sz(g[v]))
  43.     if (!u[g[v][i]])
  44.       dfs(g[v][i], value);
  45. }
  46.  
  47. void go( int l, int r, const List &v, int vn, int add_vn ) // [l, r)
  48. {
  49.   if (cnt[l] == cnt[r])
  50.     return; // no queries, only changes
  51.   if (!sz(v))
  52.   {
  53.     while (l < r)
  54.       ans[l++] = vn + add_vn;
  55.     return;
  56.   }  
  57.  
  58.   List v1;
  59.   forn(i, vn)
  60.     g[i].clear();
  61.   forn(i, sz(v))
  62.     if (v[i].a != v[i].b)
  63.     {
  64.       if (v[i].l <= l && r <= v[i].r)
  65.         add(v[i].a, v[i].b);
  66.       else if (l < v[i].r && v[i].l < r)
  67.         v1.pb(v[i]);
  68.     }
  69.  
  70.   int vn1 = 0;
  71.   forn(i, vn)
  72.     u[i] = 0;
  73.   forn(i, vn)
  74.     if (!u[i])
  75.       deg[vn1] = 0, dfs(i, vn1++);
  76.  
  77.   forn(i, sz(v1))
  78.   {
  79.     v1[i].a = color[v1[i].a];
  80.     v1[i].b = color[v1[i].b];
  81.     if (v1[i].a != v1[i].b)
  82.       deg[v1[i].a]++, deg[v1[i].b]++;
  83.   }
  84.  
  85.   vn = vn1, vn1 = 0;
  86.   forn(i, vn)
  87.     u[i] = vn1, vn1 += (deg[i] > 0), add_vn += !deg[i];
  88.   forn(i, sz(v1))
  89.   {
  90.     v1[i].a = u[v1[i].a];
  91.     v1[i].b = u[v1[i].b];
  92.   }
  93.  
  94.   int m = (l + r) / 2; // [l, m) [m, r)
  95.   go(l, m, v1, vn1, add_vn);
  96.   go(m, r, v1, vn1, add_vn);
  97. }
  98.  
  99. int main()
  100. {
  101.   #define NAME "connect"
  102.   assert(freopen(NAME ".in", "r", stdin));
  103.   assert(freopen(NAME ".out", "w", stdout));
  104.  
  105.   map <pii, int> m;
  106.   List v;
  107.   int n, k;
  108.   scanf("%d%d", &n, &k);
  109.   forn(i, k)
  110.   {
  111.     char type;
  112.     scanf(" %c", &type);
  113.     if (type == '+' || type == '-')
  114.     {
  115.       int a, b;
  116.       scanf("%d%d", &a, &b), a--, b--;
  117.       if (a == b) // loop
  118.       {
  119.         k--, i--;
  120.         continue;
  121.       }
  122.       if (a > b)
  123.         swap(a, b);
  124.  
  125.       if (type == '+')
  126.         m[mp(a, b)] = i;
  127.       else
  128.       {
  129.         int &j = m[mp(a, b)];
  130.         v.pb({a, b, j, i});
  131.         j = -1;
  132.       }
  133.     }
  134.     else
  135.       cnt[i + 1]++;
  136.     cnt[i + 1] += cnt[i];
  137.   }
  138.   forit(it, m)
  139.     if (it->second != -1)
  140.       v.pb({it->first.first, it->first.second, it->second, k});
  141.  
  142.   go(0, k, v, n, 0);
  143.  
  144.   forn(i, k)
  145.     if (cnt[i + 1] != cnt[i])
  146.       printf("%d\n", ans[i]);
  147.   return 0;
  148. }
  149.  
Runtime error #stdin #stdout #stderr 0s 12848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:102: int main(): Assertion `freopen("connect" ".in", "r", stdin)' failed.
https://ideone.com/WAe2wk
O(k log k) dynamic connectivity problem
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!