ABC126D
考えたこと
ある一点に注目する、これを白とする
その点から1ステップでたどれる点は黒でなければならない
黒から1ステップでたどれる点は白でなければならない
というわけでDFSで交互に塗ればOK
これでいい理由
任意の2点への根からの距離の合計とその2点の距離の偶奇は一致するから
似たような処理を何かで見た気がするがなんだったかなー
そうだ二部グラフ判定だ
Related Pages
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]