C - Points, Lines and Ready-made Titles
把行列看成是圖上的點， 一個點（x, y）就相當于x行 向 y列建立一條邊， 我們能得出如果一個聯通塊是一棵樹方案數是2 ^ n - 1
否則是2 ^ n。 各個聯通塊乘起來就是答案。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;
const int N = 4e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
int n, x[N], y[N], hs[N], tot;
int bin[N], fa[N], ecnt[N], pcnt[N];
int getRoot(int x) {
return x == fa[x] ? x : fa[x] = getRoot(fa[x]);
}
int main() {
for(int i = bin[0] = 1; i < N; i++) bin[i] = bin[i - 1] * 2 % mod;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &x[i], &y[i]);
hs[++tot] = x[i];
hs[++tot] = y[i];
}
sort(hs + 1, hs + 1 + tot);
tot = unique(hs + 1, hs + 1 + tot) - hs - 1;
for(int i = 1; i <= n; i++) {
x[i] = lower_bound(hs + 1, hs + 1 + tot, x[i]) - hs;
y[i] = lower_bound(hs + 1, hs + 1 + tot, y[i]) - hs;
}
for(int i = 1; i <= 2 * tot; i++) fa[i] = i, ecnt[i] = 0, pcnt[i] = 1;
for(int i = 1; i <= n; i++) {
int X = getRoot(x[i]);
int Y = getRoot(y[i] + tot);
if(X == Y) {
ecnt[X]++;
} else {
ecnt[X] += ecnt[Y] + 1;
pcnt[X] += pcnt[Y];
fa[Y] = X;
}
}
LL ans = 1;
for(int i = 1; i <= 2 * tot; i++) {
if(i != fa[i]) continue;
if(ecnt[i] < pcnt[i]) ans = (ans * (bin[pcnt[i]] - 1 + mod) % mod) % mod;
else ans = (ans * bin[pcnt[i]]) % mod;
}
printf("%lld\n", ans);
return 0;
}
/*
*/ 轉載于:https://www.cnblogs.com/CJLHY/p/10349517.html