ABC 231
Table of Contents
C - Counting 2
昇順でソートして lower_bound 使って $x_i$ 以上となる index を調べる. 二部探索用途で multiset を使うと遅いので注意.
ref: multiset vs vector
D - Neighbors
人を node, 隣り合う人の情報を edge としグラフを構築する.
node の次数が3以上のとき, またはグラフに cycle がある場合は No, それ以外は Yes を出力する.
submission code: cycle 検出方法ごとの実装
- Union Find
- 辺を作る前に両端の node が同じ親を持っているか確認する. 同じだった場合, 辺を張ると cycle を作ってしまうことがわかる.
1
|
2 -- 3
1-2, 2-3 の辺を張った状態で 1, 3 のそれぞれの親を調べると同じになる. その場合, 1-3 に辺を張ると cycle ができることがわかる.