132 lines
2.6 KiB
Java
132 lines
2.6 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Collections;
|
|
import java.util.Comparator;
|
|
import java.util.HashMap;
|
|
import java.util.HashSet;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.Set;
|
|
import java.util.TreeMap;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class E extends SimpleSavingChelperSolution {
|
|
|
|
private int[] x;
|
|
private int[] y;
|
|
private int n;
|
|
private Map<Integer, Integer> xMap;
|
|
private Map<Integer, Integer> yMap;
|
|
private List<Set<Integer>> edges;
|
|
private boolean[] visited;
|
|
private long MOD;
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
n = in.nextInt();
|
|
|
|
x = new int[n];
|
|
y = new int[n];
|
|
|
|
xMap = new TreeMap<>();
|
|
yMap = new TreeMap<>();
|
|
|
|
edges = new ArrayList<>();
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
edges.add(new HashSet<>());
|
|
}
|
|
|
|
Map<Integer, Integer> prevX = new HashMap<>();
|
|
Map<Integer, Integer> prevY = new HashMap<>();
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
x[i] = in.nextInt();
|
|
y[i] = in.nextInt();
|
|
|
|
xMap.put(x[i], xMap.getOrDefault(x[i], 0) + 1);
|
|
yMap.put(y[i], yMap.getOrDefault(y[i], 0) + 1);
|
|
|
|
Integer pX = prevX.get(x[i]);
|
|
Integer pY = prevY.get(y[i]);
|
|
|
|
if (pX != null) {
|
|
edges.get(pX).add(i);
|
|
edges.get(i).add(pX);
|
|
}
|
|
if (pY != null) {
|
|
edges.get(pY).add(i);
|
|
edges.get(i).add(pY);
|
|
}
|
|
|
|
prevX.put(x[i], i);
|
|
prevY.put(y[i], i);
|
|
}
|
|
|
|
visited = new boolean[n];
|
|
|
|
long ans = 1;
|
|
|
|
MOD = 1000000007;
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
if (visited[i]) {
|
|
continue;
|
|
}
|
|
|
|
List<Integer> res = new ArrayList<>();
|
|
dfs(i, res);
|
|
|
|
Set<Integer> usedX = new HashSet<>();
|
|
Set<Integer> usedY = new HashSet<>();
|
|
|
|
for (Integer j : res) {
|
|
usedX.add(x[j]);
|
|
usedY.add(y[j]);
|
|
}
|
|
|
|
int K = usedX.size() + usedY.size();
|
|
if (res.size() >= K) {
|
|
ans = ans * twopow(K) % MOD;
|
|
} else {
|
|
ans = ans * ((twopow(K) - 1 + MOD) % MOD) % MOD;
|
|
}
|
|
}
|
|
|
|
|
|
out.println(ans);
|
|
}
|
|
|
|
long twopow(int n) {
|
|
if (n == 0) {
|
|
return 1;
|
|
}
|
|
if (n % 2 == 0) {
|
|
long t = twopow(n / 2);
|
|
return t * t % MOD;
|
|
}
|
|
return twopow(n - 1) * 2 % MOD;
|
|
}
|
|
|
|
void dfs(int v, List<Integer> res) {
|
|
if (visited[v]) {
|
|
return;
|
|
}
|
|
visited[v] = true;
|
|
res.add(v);
|
|
|
|
for (int j : edges.get(v)) {
|
|
dfs(j, res);
|
|
}
|
|
}
|
|
}
|