2018-07-05から1日間の記事一覧
所見 グラフ上で連結かどうか->unionfind。そこから先で迷ったが、unionfindがどういうアルゴリズムかを考えると、同じ親を持つノードの数を数えればいいことがわかる。 高速な(経路圧縮した)unionfindを使えばO(K+L+NlogN)。 問題概要 N個の街が、K本の道路…
所見 グラフ上で連結かどうか->unionfind。そこから先で迷ったが、unionfindがどういうアルゴリズムかを考えると、同じ親を持つノードの数を数えればいいことがわかる。 高速な(経路圧縮した)unionfindを使えばO(K+L+NlogN)。 問題概要 N個の街が、K本の道路…