phyllo_algo https://blog.hatena.ne.jp/phyllo_algo/ れどこだ目指すよ！　(；`・ω・） https://phyllo-algo.hatenadiary.org/ その他 問題 N頂点、M辺からなる無向グラフが与えられる。(多重辺や自己ループはなし) Q個の「同じ辺を通らず、頂点aから頂点bを通って頂点cに行くことができるか？」のクエリがくるので、それに答える。 N M Q 各クエリのa,b,cは互いに異なる 考え方 行くことができないケースを考える。 a-x-c | b上記のような場合、bに行って戻るために2回辺を通らないといけない。 グラフ理論では、上記のような辺を「橋」といい、橋を含まない連結な無向グラフを「二重辺連結成分」という。 上記の問題は、二重辺連結成分に分割し、橋でそれらを連結したグラフを考えると、木になるので、木において、aからcのパスにbがあ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fphyllo-algo.hatenadiary.org%2Fentry%2F20150517%2F1431864544" title="ARC039 D. 旅行会社高橋君 - れどこだ目指すよ！　(；`・ω・）" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-05-17 21:09:04 rich https://phyllo-algo.hatenadiary.org/entry/20150517/1431864544 1.0 100%