AtCoder Beginner Contest 131：F - Must Be Rectangular!
問題
解法
頂点 X_1, X_2, ... , X_100000, Y_1, Y_2, ... , Y_100000 をおき，(x, y) に点があるとき頂点 x と y に辺を張ることを考える．こうしてできたグラフ上では長さが 3 のパスができる．このパスの始点と終点を新たに結ぶという操作が問題文中にある操作に対応する．
X と Y の二部グラフはいくつかの連結成分に分かれるが，各連結成分内は完全二部グラフになる．なぜならば，長さが 3 のパスの両端を結んでいくことで，3 という長さを奇数に拡張することができるから．具体的には，以下の図で赤〇で示したパスを通じて赤矢印の辺が新たに出来て，この赤矢印を経由して青〇で示したパスで青矢印の辺が新しくできる．
よって，3 を奇数に拡張することができた．「奇数長のパス」⇔「X - Y のパス」であるから，同じ連結成分内の X, Y は完全二部グラフになる．O(N)．
解答
二次元平面上に点を配置する系の問題では，x, y 座標をグラフの頂点としてみることで見通しが良くなることがあるらしい．
