クラスカル法クラスカル法．コストの小さい順に辺を見ていき，閉路・二重辺でなければ追加する．UnionFindを使う．バラバラの状態からはじめ，辺の頂点が同じグループに属していないなら追加すれば良い．UnionFindコストが負の辺は取り除く意味がない（すべ…

対角線上の2点を決める 対辺の数を求める 対角線上の2点を決める長方形は，対角線上の2点により一意に決まる．よって， 左上と右下の座標を決めたとき， 左下と右上の座標が集合に含まれるか判定する setのinなら$O(1)$で計算できるのがポイント．【参考】Su…