[Codeforces] A. Connect and Disconnect

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : A. Connect and Disconnect
Source            : Codeforces
Category          : Data Structure
Algorithm         : Dynamic Connectivity
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define pii             pair <int, int>  
#define mk              make_pair  
  
static const int maxn = 3e5 + 5;  
  
vector <pii> Tree[maxn * 4];  
  
void update(int node, int a, int b, int i, int j, pii p)  
{  
      if (a > j or b < i) return;  
      if (a >= i and b <= j) return void(Tree[node].push_back(p));  
      int lchild = node * 2;  
      int rchild = lchild + 1;  
      int mid = (a + b) / 2;  
      update(lchild, a, mid, i, j, p);  
      update(rchild, mid + 1, b, i, j, p);  
}  
  
int par[maxn];  
int sz[maxn];  
stack <int> st;  
int component;  
  
void makeSet()  
{  
      for (int i = 1; i < maxn; i++)  
      {  
            par[i] = i;  
            sz[i] = 1;  
      }  
}  
  
int findRep(int r)  
{  
      if (r == par[r]) return r;  
      return findRep(par[r]);  
}  
  
void marge(int u, int v)  
{  
      int p = findRep(u);  
      int q = findRep(v);  
      if (p == q) return;  
      component--;  
      if (sz[p] > sz[q]) swap(p, q);  
      par[p] = q;  
      sz[q] += sz[p];  
      st.push(p);  
}  
  
void rollback(int moment)  
{  
      while (st.size() > moment)  
      {  
            int curr = st.top(); st.pop();  
            sz[ par[curr] ] -= sz[curr];  
            par[curr] = curr;  
            ++component;  
      }  
}  
  
int ans[maxn];  
  
void dfs(int node, int a, int b)  
{  
      if (a > b) return;  
      int moment = st.size();  
      for (pii p : Tree[node]) marge(p.first, p.second);  
      if (a == b)  
      {  
            ans[a] = component;  
      }  
      else  
      {  
            int lchild = node * 2;  
            int rchild = lchild + 1;  
            int mid = (a + b) / 2;  
            dfs(lchild, a, mid);  
            dfs(rchild, mid + 1, b);  
      }  
      rollback(moment);  
}  
  
map <pii, int> in;  
vector <int> queries;  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      freopen("connect.in", "r", stdin);  
      freopen("connect.out", "w", stdout);  
  
      int n, q;  
      cin >> n >> q;  
      for (int i = 1; i <= q; i++)  
      {  
            string type;  
            cin >> type;  
            if (type == "?")  
            {  
                  queries.push_back(i);  
            }  
            else  
            {  
                  int a, b;  
                  cin >> a >> b;  
                  if (a > b) swap(a, b);  
                  if (type == "+")  
                  {  
                        in[mk(a, b)] = i;  
                  }  
                  else  
                  {  
                        int l = in[mk(a, b)];  
                        int r = i - 1;  
                        update(1, 1, q, l, r, mk(a, b));  
                        in.erase(mk(a, b));  
                  }  
            }  
      }  
      for (auto it : in)  
      {  
            int l = it.second;  
            int r = q;  
            int a = it.first.first;  
            int b = it.first.second;  
            update(1, 1, q, l, r, mk(a, b));  
      }  
      makeSet();  
      component = n;  
      dfs(1, 1, q);  
      for (int p : queries) cout << ans[p] << '\n';  
}