競プロ典型90問 083 Colorful Graph(★6)
この問題は, 平方分割と呼ばれるテクニックを用いて解くことができる.
まず, 与えられたグラフについて, あらかじめ各頂点の(出)次数を計算しておく. ここで, 今回のグラフは無向グラフであるので辺の本数が$ 2M個であることに注意して, 平方分割を行う. 具体的には, 次数が$ \sqrt {2M}以上の頂点は"大きい頂点", 次数が$ \sqrt {2M}未満の頂点は"小さい頂点"であると定義する.
すると, "大きい頂点"か"小さい頂点"かで場合分けすることにより, この問題を$ O(Q \sqrt M)で解くことができる.
"大きい頂点"
大きい頂点の数は高々$ \sqrt 2M個であることに注目すると, 色は適宜計算しておいても間に合うことがわかる. よって色をもっておき, 隣接する"大きい頂点"の色を更新していけばよい.
"小さい頂点"の場合
隣接する頂点のうち, 最も最近に更新があったものを求め, その色を出力する(これは各頂点をいつ更新したかという情報を持っておくことで高速に処理できる). そして, 隣接する"大きい頂点"の色を更新する.