srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

閉路

ARC 037 B - バウムテスト

問題 問題概要 連結成分の中で、閉路がなく、木である連結成分の個数を求める。 解法 閉路を検出する問題。dfsで探索して、すでに探索した頂点をmemoで記録しておいて、同じところに2度来たら、その連結成分は閉路を持つので木ではないのでカウントしない。 …

SRM 693 div2 easy TriangleEasy

問題 問題概要 グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。 解法 まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v の辺がある場合を考える。このとき、u - x(xはvで…

ABC 022 C - Blue Bird

問題 問題概要 省略 解法 ダイクストラでやろうと思うと、閉路の最短距離を出すのは普通にやったらできない。求めるのは0から初めて、0に戻るような閉路で最短距離。そのような経路は、0 -> u -> v -> 0 ものである。同じ道を2度通ることはできないので、u…

ABC 014 D - 閉路

問題 問題概要 木のグラフが与えられる。その木に対して、辺を1つ加えでできる、閉路の長さを答える。 解法 まず、LCAを求める。LCAについては、蟻本。多くのクエリが与えられるので、いちいち親をたどっていては、間に合わない。そこで、頂点vから、2k回上…

yukicoder No.13 囲みたい!

問題 問題概要 閉路検出 解法 考え方が悪かった。閉路検出のためにある始点から初めて、1周してその点に戻るかを判別すればいいなと思い、dfsもどきのbfsみたいなのを書き出したが完全に悪かった。閉路検出は「ある始点からスタートして、探索方向はfrom以外…

yukicoder No.19 ステージの選択

問題 問題概要 強連結成分の分解を利用する問題。強連結成分を1つの頂点に置き換えて、DAGにして、トポロジカルソートをする。 解法 N個のステージを頂点と考える。(先に指定しておくと良いステージ) -> (ステージ)の向きに有向辺をはっていき、有向グラフ…