問題概要

二次元平面上に $N$ 個の点がある。

$N$ 点から 3 個選んで、その 3 個がある長方形の 3 頂点になっているならば、残りの頂点に相当する箇所に新たに点を生やす

という操作を好きな回数だけ行うことができる。最終的に点が最大で何個できるか求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le x_i, y_i \le 10^{5}$

考えたこと

できあがるものは

長方形状に並んだ格子たち
別の長方形グループの格子は、x 座標も y 座標も共有しない

という感じになる。x 座標または y 座標を共有しているような点同士は次々と結ばれていくイメージ。なんか Union-Find を使いそう

二部グラフで表現

この手の「グリッド上のマス」だとか「二次元平面状の座標」だとかを二部グラフで表現するのは常套手段の一つではある。

左側：登場する x 座標を並べたもの
右側：登場する y 座標を並べたもの
辺：座標 (x, y) な点があるとき、左の x と右の y とを結ぶ辺に対応させる

というグラフ。こういうグラフを考える問題は本当によくある。

グラフの言葉で問題をとらえると

結局このグラフに各連結成分について完全二部グラフにする操作だということができる。よって、

二部グラフを作り
連結成分分解して
各連結成分について完全二部グラフにする

という操作になるので、追加すべき辺数も簡単に計算できる。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

const long long MAX = 110000;
long long N;
vector<long long> x, y;

long long solve() {
    UnionFind uf(MAX * 2);
    x.resize(N); y.resize(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i], uf.merge(x[i], y[i] + MAX);

    // 連結成分ごとに、左ノードと右ノードの個数を数える
    map<int, long long> mx, my;
    for (int i = 0; i < MAX; ++i) mx[uf.root(i)]++;
    for (int i = MAX; i < MAX*2; ++i) my[uf.root(i)]++;
    long long res = 0;
    for (int r = 0; r < MAX*2; ++r) res += mx[r] * my[r];
    return res - N;
}

int main() {
    cin >> N;
    cout << solve() << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 131 F - Must Be Rectangular! (青色, 600 点)

問題概要

制約

考えたこと

二部グラフで表現

グラフの言葉で問題をとらえると