格子点を2部グラフとして扱う．
点 \(\,(x,y)\,\) が与えられたとき， グラフ \(G\) において 頂点 \(v_{x}, v_{y}\) と 向無辺 \(\,\{v_{x}, v_{y}\}\,\) を作る． 点として現れる \(x\) 座標全体，\(y\) 座標全体を \(a_{x}, a_{y}\) とおく．
\(cx := \{v_{x} \in V_{G} \ \vert \ x \in a_{x} \}\), \(cy := \{v_{y} \in V_{G} \ \vert \ y \in a_{y} \}\) とおく． \(c\) に辺を追加して完全グラフにしたいので， \(\#cx \cdot \#cy = \#E(c) + \) (張られる辺の本数) \( \cdots (*)\) となる． よって， \(G\) の連結成分 \(c\) に対する答え = 張られる辺の本数 = \(\#cx \cdot \#cy - \#E(c)\) となる． ゆえに，\(G\) 全体での答えは \( \sum_{c} (\#cx \cdot \#cy - \#E(c)) = \sum_{c} (\#cx \cdot \#cy) - \#E(G) \) となる．
説明
上の方法で計算できる理由を説明する． 以下の場合分けで，いずれのケースも式 \((*)\) が成り立つ．
- 長さが 1の path しかないとき． これは \(c\) が既に完全2部グラフ．
- 長さが 2の path しかないとき． これは \(c\) が既に完全2部グラフ．
- 長さが 3以上の path が存在するとき． 辺の長さの偶奇に依らず， 辺の追加を帰納的に行うことで， \(p\) を完全2部グラフにできる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
map<ll,vll> to;
const ll C = 1e5 + 5;
vll vx;
rep(i,n){
ll x,y; cin >> x >> y;
y += C;
to[x].push_back(y);
to[y].push_back(x);
vx.push_back(x);
}
map<ll,bool> vis;
ll cx = 0, cy = 0;
if(vis[cu]) return;
vis[cu] = true;
if(cu < C) cx++;
else cy++;
dfs(dfs, ne, cu);
}
};
ll ans = -n;
rep(i,n) {
cx = cy = 0;
dfs(dfs, vx[i]);
ans += cx * cy;
}
cout << ans << endl;
return 0;
}
