ABC131 F - Must Be Rectangular! (600)

F - Must Be Rectangular!

概要

2次元平面上にN個の点がプロットしてある。i番目の点の座標は(x[i], y[i])と表される。以下の操作を可能な限り繰り返す。

• 次のような任意の4か所(a, c), (a, d), (b, c) , (b, d)のうち、ちょうど3か所に点がプロットしてある場合、残りの1か所にも点をプロットする

このとき追加される点の個数を求めよ。

制約

1 ≦ N ≦ 10^5
1 ≦ x[i], y[i] ≦ 10^5

方針

点がプロットされているy方向の2直線(x = a, x = b) (a ≠ b)を考える。2つの直線を直線a, 直線bとよぶ。
この直線上にそれぞれプロットされている点について、もしy座標が一致しているものがある場合、この2直線は「同期」され、最終的に直線a上に点(a, c)があれば直線b上に(b, c)がプロットされ、逆に直線b上に点(b, d)があれば直線a上に点(a, d)がプロットされる。

効率的に考える方法として、座標を次のようなグラフに変換する。

• x1, x2, ... x100000, y1, y2, ..., y100000と番号付けられた200000個の頂点を準備
• 点(a, b)にプロットがあるとき、またその時に限り頂点xaと頂点ybに辺を結ぶ

このとき、このグラフは2部グラフとなる。(x側、y側でそれぞれグループとなり、x側同士もしくはy側同士の頂点を結ぶ辺は存在しない)

点を追加プロットしていく操作は上記の2部グラフについて長さ3のパスがあった時に始点と終点を結ぶ操作にあたる。この操作を繰り返し行うと、上記グラフは連結成分ごとに完全2部グラフを構成する。

完全2部グラフの辺の数は、x側の頂点数をxcnt, y側の頂点数をycntとするとxcnt * ycntであるため、連結成分ごとにDFSしてこの数値を求め、全てを足したものからNを引いたのが求める数値である。

感想

解説放送通りです。

解答

Submission #7697835 - AtCoder Beginner Contest 131

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
typedef long long int ll;
using namespace std;
 
const int V = 101010;
vector<int> to[2*V];
vector<int> cnt;
bool visited[2*V];
 
void dfs(int v){
    if(visited[v]) return;
    visited[v] = true;
    cnt[v/V]++;
    for(int u : to[v]) dfs(u);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	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;
    for(int i = 0; i < 2 * V; i++){
        if(visited[i]) continue;
        cnt = vector<int>(2);
        dfs(i);
        ans += (ll) cnt[0] * cnt[1];
    }
 
    cout << ans - n << endl;
}