cross(idy002的神奇并查集）

纵坐标相同的点连边，横坐标相同点点连边。

不在同一个联通块的点互不影响，所以可以用乘法原理把每一块的答案乘起来。

对于一块，有多少个不同的x就有多少条与y轴平行的直线，记为x条；有多少个不同的y就有多少条与x轴平行的直线，记为y条。所以总直线数是x+y条。每条直线可以选或不选，所以每个联通块的答案为2^(x+y).但是对于边数比点数小的联通块来说（边数=点数-1），x+y = 点数+1，不可能出现全部直线都选的情况（每个点最多只能有一条直线)，所以这种情况答案为2^(x+y) - 1;

#include<bits/stdc++.h>
using namespace std;
const int mod  = 1e9+7;
map<int,vector<int> >mpx,mpy;
vector<int>seq[100005],sex[100005],sey[100005];
int n,x[100005],y[100005],fa[100005];
long long ans;
long long mpow(long long a,long long b)
{
	long long rt = 1;
	for( ; b; b >>= 1, a = (a * a)%mod)
	{
		if(b & 1) rt = (rt * a)%mod;
	}
	return rt;
}
int  find(int x)
{
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}
void unio(int x,int y)
{
	int r1 = find(x);
	int r2 = find(y);
	fa[r1] = r2;
}
void uniqu(vector<int> &vc)
{
	sort(vc.begin(),vc.end());
	vc.erase(unique(vc.begin(),vc.end()),vc.end()); 
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		fa[i] = i;
		scanf("%d%d",&x[i],&y[i]);
		mpx[x[i]].push_back(i);
		mpy[y[i]].push_back(i);
	}
	for(map<int,vector<int> >::iterator it = mpx.begin() ;it != mpx.end();++it)
	{
		pair<int,vector<int> > p = *it;
		vector<int> &vc = p.second ;
		for(int i = 1; i < (int)vc.size(); i++)
		{
			unio(vc[i-1],vc[i]);
		}
	}
		for(map<int,vector<int> >::iterator it = mpy.begin() ;it != mpy.end();++it)	
	{
		pair<int,vector<int> > p = *it;
		vector<int> &vc = p.second ;
		for(int i = 1; i < (int)vc.size(); i++)
		{
			unio(vc[i-1],vc[i]);
		}
    }        
		for(int i = 1; i <= n ; i++)
		{
			int r = find(i);
			seq[r].push_back(i);
			sex[r].push_back(x[i]);
			sey[r].push_back(y[i]);
		}
		ans  = 1;
		for(int i = 1; i <= n ;i++)
		{
			if(i != find(i)) continue;
			uniqu(sex[i]);
			uniqu(sey[i]);
			int tot =  (int)seq[i].size();
			int tot1 = (int)sex[i].size() + (int)sey[i].size();
			if(tot == tot1 -1 )
			{
				ans=ans * (mpow(2,tot1) -1 +mod)%mod;
			}
			else ans = ans * mpow(2,tot1) %mod;
		}
		cout << ans;
		return 0;
}