srupのメモ帳

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

強連結成分分解

yukicoder No.470 Inverse S+T Problem

問題 問題概要 3つの文字でできている文字列があたえられる.それらを前後で分けて、すべての文字列が相異なるように分けられるなら分けろ。 解法 考察として、文字を分けるのは1-2または2-1の2通りしかないので、2n通りすべてを調べれば答えが求まることがわ…

yukicoder No.19 ステージの選択

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

aoj GRL_3 Connected Components - Strongly Connected Components

問題 問題概要 強連結成分分解する問題。 解法 強連結成分を分解するアルゴリズムとして、Kosarajuというものがある。今回はそれを使って、実装した。アルゴリズム自体は下のサイトを見てもらえれば、分かりやすい。 mathtrain.jp ミス アルゴリズム自体の理…