CodeChef SnackDown 2021 Online Qualifiers - Minimise Difference

• 問題
• AC

問題: 無向グラフが与えられる。出次数の最大値が最小であるようなacyclic orientationを求めよ。

出次数が$D$以下であるacyclic orientationが存在するかどうかの判定問題が解ければよい。判定問題は次のように解ける:

まだ選んでいない頂点の中でトポロジカル順序で先頭にする頂点$v$を自由に選ぶ。この$v$の次数は$D$以下でなければならず、そのような頂点が存在しなければ判定はNOである。存在する場合、$v$から伸びているすべての辺を削除する。以上を頂点の数だけ繰り返す。実装はキューで${O}(N)$でできる。