算法
(二分图、dfs)
我们可以将每个点 $(x, y)$ 拆成两个点 $x$ 和 $y$,再将 $x$ 和 $y$ 连一条无向边
这样原问题就被抽象成了一个图论问题,而且还是个二分图。相应的操作就变成了已知 $a — b, a — d, c — b, c — d$ 中的三条边,然后添加剩余的一条边。
对于每个连通分量的答案(其实就是把当前联通分量对应的二分图变成完全二分图所需加的边数),我们可以用 $dfs$ 来求出它在 $x$ 方向上的点数和 $y$ 方向上的点数,求出二者的乘积,就是相应的完全二分图的边数,再减去当前连通分量上的边数即可。
所以,我们可以先计算出所有连通分量所对应的完全二分图的边数之和,再减去已知的边数,从而得到答案。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
const int V = 100005;
vector<int> to[V * 2];
bool visited[V * 2];
vector<int> cnt;
void dfs(int v) {
if (visited[v]) return;
visited[v] = true;
cnt[v/V]++;
for (int u : to[v]) dfs(u);
}
int main() {
int n;
cin >> n;
rep(i, n) {
int x, y;
cin >> x >> y;
y += V;
to[x].push_back(y);
to[y].push_back(x);
}
ll ans = 0;
rep(i, V * 2) {
if (visited[i]) continue;
cnt = vector<int>(2);
dfs(i);
ans += (ll)cnt[0] * cnt[1];
}
ans -= n;
cout << ans << '\n';
return 0;
}