かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC216 D - Pair of Balls

ABC グラフ 典型 競技プログラミング 解説

問題はこちら

問題概要

{2N}個のボールがあり，各ボールには{1}から{N}以下の整数が書かれたボールはちょうど2個ずつ存在する．{M}本の筒があり，各筒にはボールが{k_i}個入っている．異なる{2}本の筒の一番上にあるボールの色が同じ場合それらを取り出せる．すべての筒を空にできるか判定せよ．

{1\leq N\leq 2×10^5\\ 2\leq M\leq 2×10^5\\ 1\leq k_i\\ 1\leq a_{i,j}\leq N\\ \sum_{i=1}^{M}=2N}

解説

頂点{a_{i,j}}から頂点{a_{i,j+1}}に辺を張ったグラフを考えます．
このグラフに閉路があるなら答えはNo. 閉路がなければYesとなります．
なぜならば，{a_{i,j+1}}を出すためには{a_{i,j}}を出す必要があり，グラフに閉路があるということはデッドロックのような状況になっているということなのでその頂点を取り出すことはできないからです．逆に，閉路がなければトポロジカル順に取り出すことができます．

提出プログラム

https://atcoder.jp/contests/abc216/submissions/25449130
https://atcoder.jp/contests/abc216/submissions/25451462 ACL

感想