考えたこと

高々10^6頂点で、最悪10^3回処理をする

毎回全頂点をチェックすると10^9で間に合わないがそんなことはしない

幅優先探索すれば10^6オーダーで処理が終わるのでOK

無意識に問題を書き換えてた

「すべての白マスの内、黒マスに隣接しているものを黒にする」は「すべての黒マスについて、隣接マスに白マスがあるなら、それを黒にする」と同じ

確かにこの言い換えに気づかなければ悩んだかもな

後者では一度処理した黒マスは周囲に白マスがなくなるので二度と処理する必要がない、これがオーダーが減る原理