872E - Points Lines and Ready-made Titles - CodeForces Solution

#include <stdlib.h>
#include <time.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <fstream>
#include <string>
#include <string.h>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <set>
#include <deque>
using namespace std;
typedef long long int ll;
const int M=200000+10;
 
ll mod = 1e9 + 7;
int x[M],y[M];
set<int> sx,sy;
map<int,int> mpx,mpy;

int pa[M];
int pan[M];
int pae[M];
int fpa(int x){
    return pa[x] = ( x == pa[x] ? x : fpa(pa[x]) );
}

ll two[M];
set<int> ss;
 int main() {
	
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	
  two[0] = 1;
   for(int i = 1; i < M; i++) two[i] = (two[i - 1] * 2) % mod;
	int n;
	cin>>n;
	for (int i = 1; i <= n; i++){
		cin>>x[i]>>y[i];
     sx.insert(x[i]); sy.insert(y[i]);
	}
   int cntx = 1;
	for(set<int>::iterator it = sx.begin(); it != sx.end(); it++){
       int v = (*it);
       mpx[v] = cntx++;
  }
  cntx--;
  int cnty = 1;
  for(set<int>::iterator it = sy.begin(); it != sy.end(); it++){
       int v = (*it);
       mpy[v] = cnty++;
  }
  cnty--;

  for(int i = 1; i < M; i++){
      pa[i] = i; pan[i] = 1;
  }
	for(int i = 1; i <= n; i++){
       int mx = mpx[x[i]]; int my = mpy[y[i]];
       int u = mx; int v = my + cntx;
       int pu = fpa(u); int pv = fpa(v);
       if(pu == pv){
           pae[pu]++;
       } else {
            pan[pu] = pan[pv] + pan[pu];
            pae[pu] = pae[pv] + pae[pu] + 1;
            pa[pv] = pu;
        }
  }
for(int i = 1; i <= cntx + cnty; i++){
       ss.insert(fpa(i));
  }
   ll res = 1;
  for(set<int>::iterator it = ss.begin(); it != ss.end(); it++){
       int v = (*it); ll tot;
       if(pan[v] == pae[v] + 1){
             tot = two[pan[v]] - 1;
       } else {
             tot = two[pan[v]];
        }
        res = (res * tot) % mod;
        if(res < 0) res += mod;
  }
   cout<<res<<endl;
	
	return 0;
}