yukicoder - No.1293 2種類の道路
解説
UnionFindUndoを持っていますか？僕は持っています。
道路と歩行者でそれぞれ頂点を用意し、それぞれ道路のみ歩行者のみいけるところをつなげておきましょう。
ここで、頂点1の場合で考えてみましょう。
1において、道路のみをつかっていける集合をとします
に属する全ての要素を歩行者側にいくことができるので、辺をはります。
そうすると、頂点数になるので、全体でいける数がわかります。
これがについて全部いえるので
についてはまとめて計算しちゃいましょう。
Undo可能なUnionFindを用いて計算量はです
自分自身も含まれることに注意してね
