https://kanpurin.hatenablog.com/entry/2021/08/29/230502

問題概要

${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

ABC216 D - Pair of Balls

問題概要

解説

提出プログラム

感想