[Spoj] DYNACON1 - Dynamic Tree Connectivity

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DYNACON1 - Dynamic Tree Connectivity
Source            : Spoj
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;  
  
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;  
      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;  
      }  
}  
  
bool ans[maxn];  
pii query[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)  
      {  
            if (query[a].first > 0)  
            {  
                  int u = query[a].first;  
                  int v = query[a].second;  
                  ans[a] = findRep(u) == findRep(v);  
            }  
      }  
      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  
  
      int n, q;  
      cin >> n >> q;  
      for (int i = 1; i <= q; i++)  
      {  
            string type;  
            int a, b;  
            cin >> type >> a >> b;  
            if (a > b) swap(a, b);  
            assert(a != b);  
            if (type[0] == 'c')  
            {  
                  queries.push_back(i);  
                  query[i] = mk(a, b);  
            }  
            else if (type[0] == 'r')  
            {  
                  if (!in.count(mk(a, b))) continue;  
                  int l = in[mk(a, b)];  
                  int r = i;  
                  update(1, 1, q, l, r, mk(a, b));  
                  in.erase(mk(a, b));  
            }  
            else  
            {  
                  if (in.count(mk(a, b))) continue;  
                  in[mk(a, b)] = i;  
            }  
      }  
      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();  
      dfs(1, 1, q);  
      for (int p : queries) cout << (ans[p] ? "YES" : "NO") << '\n';  
}