F - Well-defined Path Queries on a Namori Editorial by Kazu1998k
今回の問題は \(N\) 頂点, \(N\) 辺の連結グラフでしたが, 実は一般のグラフ (非連結, 非単純の場合も含む) の場合でも \(N\) 頂点 \(M\) 辺のグラフにおいて 前計算 \(O(N+M)\) 時間, 1クエリあたり \(O(1)\) 時間で判定できる必要十分条件がわかっています. 私が作成した問題ですが, 興味のあるかたはぜひ解いてみてください.
[問題] yukicoder No 1983 南の島のマーメイド
[解説] 解説 PDF (※ 18ページから)
略解 (証明などは解説から見てください)
以下の同値な条件に帰着される.
- 橋のみからなる部分グラフ上で連結である.
- グラフに存在するサイクル基底になる辺を全て取り除いたグラフ上で連結である (こちらの条件は前計算が \(O((N+M) \log N)\) 時間になる).
posted:
last update: