Prelude
真是一道好题，然而比赛的时候花了太多时间在B题上，没时间想这个了QAQ。
题目链接：萌萌哒传送门（。＾▽＾）
Solution
观察样例和样例解释，我们发现，假如有四个点，恰好占据在某一个矩形的四个顶点上，那么这个矩形的四条边，都是可以自由选择画或者不画的。
这时候，我们称这四个点每个点“控制”了四条直线中的一条，可以自由选择这条直线画或者不画。这里可以配合样例解释理解一下。
考虑建立常用的图论模型——行列模型，把每一行抽象成一个点，每一列抽象成一个点，假如在\((x,y)\)处有一个点，那么用一条边连接第\(x\)行和第\(y\)列所代表的点。
在这个图上，每条边可以选择“控制”她所连接的两个点中的一个。
再次观察样例，发现如果四个点恰好占据在一个矩形的四个顶点上，那么这个连通块内会有一个环。
紧接着我们发现，如果在建出来的图上，某个连通块内有一个环的话，那么这个连通块内的每一个点，都可以被一条边“控制”，并且这些边不会重复。
也就是说，这个连通块内的每一个点所代表的直线，都是可以自由选择画或者不画的，因此，假设这个连通块内的点数为\(n\)，则这个连通块内的方案数为\(2^{n}\)。
假如某一个连通块内没有环，即形成了一棵树，那么容易发现，只有“所有直线都画”这一种情况没法办到，因此，方案数为\(2^{n}-1\)。
根据乘法原理，每个连通块之间互不干扰，所以把每个连通块的方案数乘起来就好了。
Code
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cctype>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXN = 200010;
const int MOD = 1e9+7;
int read() {
int x = 0, ch;
while( isspace(ch = getchar()) );
do x = x * 10 + ch - '0';
while( isdigit(ch = getchar()) );
return x;
}
int n;
map<int,int> idx, idy;
int nid;
namespace G {
int head[MAXN], nxt[MAXN], to[MAXN], m;
void init() {
memset(head, -1, sizeof head);
}
void adde( int u, int v ) {
to[m] = v, nxt[m] = head[u], head[u] = m++;
to[m] = u, nxt[m] = head[v], head[v] = m++;
}
}
int fpow( int a, int b ) {
int c = 1;
while(b) {
if( b & 1 ) c = int(1LL * c * a % MOD);
a = int(1LL * a * a % MOD);
b >>= 1;
}
return c;
}
int vis[MAXN];
queue<int> q;
int solve( int s ) {
using namespace G;
int e = 0, o = 0; // 边数和点数
vis[s] = 1, q.push(s);
while( !q.empty() ) {
int u = q.front(); q.pop();
++o;
for( int i = head[u]; ~i; i = nxt[i], ++e )
if( !vis[to[i]] )
vis[to[i]] = 1, q.push(to[i]);
}
e >>= 1;
return e == o-1 ? (fpow(2, o) - 1 + MOD) % MOD : fpow(2, o);
}
int main() {
n = read();
G::init();
for( int i = 0; i < n; ++i ) {
int x = read(), y = read();
if( !idx[x] ) idx[x] = ++nid;
if( !idy[y] ) idy[y] = ++nid;
G::adde(idx[x], idy[y]);
}
int ans = 1;
for( int i = 1; i <= nid; ++i )
if( !vis[i] )
ans = int(1LL * ans * solve(i) % MOD);
printf( "%d\n", ans );
return 0;
}