Atcoder ABC 131F（图论）

把每一个 $x$ 坐标当作一个 vertex，每一个 $y$ 坐标也当作一个 vertex。

每个平面上的点当作一个 edge：例如一个点为 $(x_i,y_i)$，就把 $x_i$ 和 $y_i$ 之间连一个 edge。

我们会发现：一个包含4个点的长方形，刚好就是 4个vertex + 4个edge。所以有：

能够加一个点 $\iff$ 4个点连通，且只有3个edge。

扩展一下，如果有 $n$ 个 $x$ 坐标和 $m$ 个 $y$ 坐标形成同一个连通块，那么我们最多可以有 $n \times m$ 个点（edge）（长方形中的每一个点都被填上了）。

所以，用并查集维护一下所有点形成的连通块，然后找到每个连通块的 $x,y$ 坐标个数。最终减去所有edge数量，即：

$$ans = \sum\limits_i (n_i \times m_i) - e$$

这题主要是学习一下 以坐标为 vertex，点为 edge 的思想

using namespace std;
#include <bits/stdc++.h>

const int maxn = 2e5+5;
const int maxm = 1e5;
 
int n;
int par[maxn];  // [1...1e5] 储存x坐标，[1e5+1...2e5] 储存y坐标
int l[maxn], r[maxn];  //记录每个par对应的块有几个x，y坐标
 
int finds(int u) {
    if (par[u] == u) return u;
    return par[u] = finds(par[u]);
}
 
void unions(int u, int v) {
    u = finds(u), v = finds(v);
    if (u > v) swap(u,v);
    par[v] = u;
}
 
int main() {
 
    cin >> n;
    for (int i = 1; i <= 2*maxm; i++) par[i] = i;
    for (int i = 1; i <= n; i++) {
        int x,y; cin >> x >> y;
        unions(x, y+maxm);  // y坐标对应的是 y+1e5
    }
    for (int i = 1; i <= maxm; i++) {
        int u = finds(i);  // x坐标
        l[u]++;
        u = finds(i+maxm);  // y坐标
        r[u]++;
    }
 
    ll ans = 0;
    for (int i = 1; i <= 2*maxm; i++) {
        ans += (ll)(l[i]) * (ll)(r[i]);
    }
    ans -= n;
    cout << ans << endl;
}