2次元座標と二部グラフ - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

二次元座標を二部グラフとみなすのは典型テクニックとして知られていて、蟻本にも中級編第三章に乗ってる。
以下がその考え方の概要である。

概要

このようにx軸とy軸の位置ごとに、二部グラフにする。
例は(x, y) = (1, 2)とすると、その点の位置を辺として両側の頂点とつなげる
 
x軸　　　　　　　y軸
x=0 〇　　　　 〇  y=0
 
x=1 〇---　　　〇  y=2
        |----
x=2 〇　　　 |-〇  y=2
 
 
 

二部グラフとみなすことで、二部グラフの最大マッチングなどに帰着しやすい。そうでなくとも、二部グラフの完全グラフなどの性質を思いつきやすい。

例　ABC131 F(600) Must Be Rectangular!

https://atcoder.jp/contests/abc131/tasks/abc131_f

この問題では、先ほどの考え方を使うと、x軸側の頂点２つ、y軸側の頂点二つ間それぞれに辺を引かれた状態、つまり(x1, y1), (x2, y1), (x1, y2), (x2, y2)に点が打たれてる状態にしたい。この状態をXとする。
これをもとに考察を進めると、上記で定義したグラフで、x軸側とy軸側でつながってるひとかたまりは、いい感じに辺（つまり2次元平面上での点）を追加すると、全部のx軸側とy軸側の点の組み合わせにおいて、Xの状態を達成できるとわかる。これは二部グラフの完全マッチングそのものである。
つまり、この問題は上記の考え方を入口に、ひとかたまりずつ、二部グラフの完全マッチング数を求めて、それの和を求めてから最初にすでにあるN個の点を引けばいいとわかる。

ちなみにひとかたまりを考察するときに使う典型として、「Union Find木」があり、今回もこれを使うとスッキリ実装できる。けんちょん先生参照すべし。