ABC 401-500/ABC401E - Reachable Set - 競技プログラミング用 知識集積所

---

問題

ABC401E

必要知識

B以下レベルの内容は省略

• 隣接リスト（未作成）
• UnionFind木（未作成）

考え方

頂点を3つのグループにわけて考える。

• グループA：番号がk以下である頂点
• グループB：グループAの頂点と隣接している頂点
• グループC：残り

kという値に対して答えるべきは、

• グループAが全部連結であれば、グループBの個数
• グループAが連結でなければ、不可能なので-1

である。

まず、グループAについてはUnionFind木（未作成）を用いて考えればよい。
ただし、毎回0から順に連結判定をしていくとTLEしてしまう。
一度連結になったものはもう非連結には戻らないことを利用して、前回最初に非連結だった番号から判定スタートすることで高速化する。

グループBについては、グループAに頂点が加わるたびに、それを削除して、同時にそれに隣接していてグループAにいないものを加えていけばよい。

いずれの処理でも隣接する頂点全てを高速で処理する必要があるため、まず最初に隣接リスト（未作成）を作っておく必要がある。

解答例

解答例

注意点

別解