ABC 131 F - Must Be Rectangular!

問題

座標平面上に与えられた $n$ 個の点 $(X _ i , Y_ i )$ について、長方形の $3$ 頂点をなすような $3$ 点があれば残りの $1$ 点を追加する、という操作が最大で何回行えるか求めよ。（$n\leq 10 ^ 5,\ 1\leq X _ i, Y _ i \leq 10 ^ 5$）

atcoder.jp

解説

$x$ 座標に現れる数字と $y$ 座標に現れる数字がかぶらないようにするために、平行移動して $0\leq X _ i < 10 ^ 5 \leq Y _ i < 2 \times 10 ^ 5$ とする。
$2n$ 個の点 $X _ 0 , Y_ 0, \ldots ,X _ {n - 1}, Y _ {n - 1}$ を 頂点とするグラフを考えて、点 $(x,y)$ を辺とみなすと、 点を追加して長方形を作る操作は辺を追加して各連結成分を部分完全二部グラフにすることと同じである。各連結成分について、$x$ 座標、$y$ 座標に対応する点がそれぞれ $a,b$ 個あったとき、辺は $a\times b$ 本引くことができるので、すべての連結成分について和をとったものから、もとの辺の本数 $n$ を引いたものが可能な操作回数となる。

実装

連結成分への分解は Union Find を使った。また、 $R$ という辞書を用意し、$R[r]$ は $r$ を根とする連結成分の ($x$ 座標に対応する点の集合, $y$ 座標に対応する点の集合) を表している。

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [None]*n

    def root(self, x):
        if self.parent[x] == None:
            return x
        else:
            return self.root(self.parent[x])

    def union(self, x, y):
        x0 = self.root(x)
        y0 = self.root(y)
        if x0 == y0:
            return
        if x0 > y0:
            x0, y0 = y0, x0
        self.parent[y0] = x0


n = int(input())
m = 10**5
uf = UnionFind(2*m)
X, Y = [], []
for i in range(n):
    x, y = map(int, input().split())
    X.append(x-1)
    Y.append(y-1+m)
    uf.union(x-1, y-1+m)
R = {}
for x, y in zip(X, Y):
    r = uf.root(x)
    try:
        R[r][0].add(x)
        R[r][1].add(y)
    except:
        R[r] = ({x}, {y})
ans = 0
for r in R.keys():
    ans += len(R[r][0])*len(R[r][1])
print(ans-n)

atcoder.jp