ARC065 D 連結 / Connectivity

所見

グラフ上で連結かどうか->unionfind。そこから先で迷ったが、unionfindがどういうアルゴリズムかを考えると、同じ親を持つノードの数を数えればいいことがわかる。
高速な(経路圧縮した)unionfindを使えばO(K+L+NlogN)。

問題概要

N個の街が、K本の道路とL本の線路でつながっている。街iについて、道路でも線路でもつながっている街の個数を数えよ。

取った方針

グラフ上で連結かどうかを高速に答えるにはunion-findを使う。
道路、線路をそれぞれエッジとするグラフを考える。それらをグラフG、Hとすると、それぞれのグラフについて街iから街jに行けるかどうかがO(logN)で求まる。
繋がっている、というのは、unionfindにおいて、同じ親を持つ、ということであるので、線路でも道路でも繋がっている、という事はノードiとノードjがGにおいてもHにおいても同じ親を持つことに他ならない。
(Gにおける親, Hにおける親)をキーとするmapをO(NlogN)で用意すれば、同じ親を持つノードがいくつあるかをO(logN)で求めることができるので、事前計算O(K+L+NlogN)、解答O(NlogN)で求められ、これは間に合う。

正しい方針

同上

得られた知見

・グラフのノードが連結かどうかを聞かれたらunionfindの利用を考える。
・unionfindにおいて、連結である、とは同じ親を持つことを意味する。

解くのに必要な要素

・unionfind
・unionfindの持つ意味

周辺調査によって得られた知見

・特になし