yukicoder No.812 Change of Class - アルゴリズマーの備忘録

競プロコンテストの季節になってしまったので、ゆきこだ解いてリハビリするよー

N頂点M辺の無向グラフが与えられる。毎日A-B-Cとパスが存在する場合A-C間に辺が生える。Q個のクエリが与えられるので、それぞれ「最終的にその頂点に隣接する頂点数はいくつか。またその頂点数になるのに何日要するか」を求めよ。

まず最終的な頂点数だけど、これは連結頂点数(それはそう)

で、Q≦30と小さいので毎回BFSをすると、一番遠い頂点までの距離も同時に求まります。A-B-C-D-EのA-E間の距離は4ですが、連結になるまでA-C-E→A-Eとつながるのでceil(log)を取りましょう。

えー…適当に☆2.5から解いたらリハビリとして簡単過ぎました…☆3以上行きます…

実は昨日その次の問題 No.813 ユキちゃんの冒険 - yukicoder を解いたのですが、誤読で死んでいたので「少し難易度落とすかぁ…」ってやった結果です。