fork download
copy 
  1. // Day Created: apr 8th 2026
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <map>
  6.  
  7. #define fname "."
  8. #define ll long long
  9. #define fi first
  10. #define se second
  11.  
  12. using namespace std;
  13. int n, m;
  14. int res[300005];
  15.  
  16. map<pair<int, int>, int> mp;
  17. struct Queries {
  18.     char t;
  19.     int u, v;
  20. };
  21.  
  22. struct DSU {
  23.     int par[300005], sz[300005], scc;
  24.     vector<pair<int &, int>> history;
  25.     DSU(int n) {
  26.         scc=n;
  27.         for(int i=1; i<=n; ++i) par[i]=i, sz[i]=1;
  28.     }
  29.  
  30.     int find_root(int u) {
  31.         return par[u]==u?u:find_root(par[u]);
  32.     }
  33.  
  34.     void join_set(int u, int v) {
  35.         u=find_root(u), v=find_root(v);
  36.         if(u==v) return;
  37.         if(sz[u]<sz[v]) swap(u, v);
  38.         history.emplace_back(sz[u], sz[u]);
  39.         history.emplace_back(par[v], par[v]);
  40.         history.emplace_back(scc, scc);
  41.         sz[u]+=sz[v], par[v]=u, --scc;
  42.     }
  43.  
  44.     void rollback(int until) {
  45.         while((int)history.size()>until) 
  46.             history.back().fi=history.back().se, 
  47.             history.pop_back();
  48.     }
  49.  
  50. } dsu(0);
  51.  
  52. vector<Queries> tree[4*300000+5];
  53. void update(int id, int l, int r, const int &u, const int &v, const Queries &q) {
  54.     if(l>v || r<u) return;
  55.     if(l>=u && r<=v) {
  56.         tree[id].emplace_back(q);
  57.         return;
  58.     }
  59.     update(id<<1, l, (l+r)>>1, u, v, q);
  60.     update(id<<1|1, ((l+r)>>1)+1, r, u, v, q);
  61. }
  62.  
  63. void get(int id, int l, int r) {
  64.     int snapshot=dsu.history.size();
  65.     for(const auto &[t, u, v]:tree[id]) 
  66.         if(t=='+') dsu.join_set(u, v);
  67.     if(l==r) 
  68.         for(const auto &[t, u, v]:tree[id]) 
  69.             if(t=='?') cout<<dsu.scc<<'\n';
  70.     else 
  71.         get(id<<1, l, (l+r)>>1), 
  72.         get(id<<1|1, ((l+r)>>1)+1, r);
  73.     dsu.rollback(snapshot);
  74. }
  75.  
  76. main() {
  77.     if(fopen(fname"inp", "r")) {
  78.         freopen(fname"inp", "r", stdin);
  79.         freopen(fname"out", "w", stdout);
  80.     }
  81.     cin.tie(0)->sync_with_stdio(0);
  82.     cin>>n>>m;
  83.     dsu=DSU(n);
  84.     for(int i=1; i<=m; ++i) {
  85.         char t; int u, v;
  86.         cin>>t;
  87.         Queries q;
  88.         if(t!='?') {
  89.             cin>>u>>v;
  90.             q={t, u, v};
  91.             if(t=='+') mp[{u, v}]=i;
  92.             else 
  93.                 update(1, 1, m, mp[{u, v}], i-1, q), 
  94.                 mp[{u, v}]=-1;
  95.         }
  96.         else q={t, 0, 0}, update(1, 1, m, i, i, q);
  97.     }
  98.  
  99.     get(1, 1, m);
  100. }
Success #stdin #stdout 0.01s 35076KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3EzdIJ
language:
C++ (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!