292D - Connected Components - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

const int N = 505, M = 1e4+5;
int par[2][M][N], sz[2][M][N]; // for prefix

int root(int v, int i, bool j)
{
  if(par[j][i][v]==-1) return v;
  return par[j][i][v] = root(par[j][i][v], i, j);
}
inline void merge(int u, int v, int i, bool j)
{
  u = root(u, i, j);
  v = root(v, i, j);
  if(v==u)
    return;
  if(sz[j][i][u] > sz[j][i][v])
    swap(u, v);
  par[j][i][u] = v;
  sz[j][i][v] += sz[j][i][u];
}

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i=0;i<n;i++)
    {
      sz[1][m][i] = sz[0][0][i] = 1;
      par[1][m][i] = par[0][0][i] = -1;
    }
  vector<pair<int,int> > e;
  for(int i=0;i<m;i++)
    {
      int u, v;
      cin >> u >> v;
      u--;v--;
      for(int j=0;j<n;j++)
	{
	  sz[0][i+1][j] = sz[0][i][j];
	  par[0][i+1][j] = par[0][i][j];
	}
      merge(u, v, i+1, 0);
      e.push_back({u, v});
    }
  while(e.size())
    {
      int u = e.back().first, v = e.back().second;
      e.pop_back();
      int j = e.size();
      for(int i=0;i<n;i++)
	{
	  sz[1][j][i] = sz[1][j+1][i];
	  par[1][j][i] = par[1][j+1][i];
	}
      
      merge(u, v, j, 1);
    }
  int k;
  cin >> k;
  for(int i=0;i<k;i++)
    {
      int l, r;
      cin >> l >> r;
      int cnt = 0;
      // use par[0][M-1][N-1] and sz[0][M-1][N-1]
      for(int i=0;i<n;i++)
	{
	  par[0][M-1][i] = -1;
	  sz[0][M-1][i] = 1;
	}
      for(int i=0;i<n;i++)
	{
	  if(par[0][l-1][i]!=-1)
	    merge(i, par[0][l-1][i], M-1, 0);
	  if(par[1][r][i]!=-1)
	    merge(i, par[1][r][i], M-1, 0);
	}
      for(int i=0;i<n;i++)
	cnt += (par[0][M-1][i]==-1);
      cout << cnt << endl;
    }
  return 0;
}