最初、頂点にアルファベット、辺に文字列を乗せたグラフを考えていたが、うまく解けなかった。 頂点に文字列を乗せて、しりとりが成立する箇所に辺を張ったグラフを考えるとうまくいった。 問題へのリンク 問題概要 英大文字 2 文字からなる 個の文字列 が与…

「与えられたグラフを強連結成分分解すると DAG になるので、DAG 上で DP する」というのが想定解だが、フローでも解けると話題になった問題！ 問題へのリンク 問題概要 頂点数 の有向グラフがある。最初、すべての頂点は白色である。以下の操作を 2 回行う…

強連結成分分解の verify 問題へのリンク 問題概要 単純とは限らない、頂点数 、辺数 の有向グラフが与えられる。 このグラフを強連結成分分解して、トポロジカルソート順に出力せよ。 制約 解法 まず、強連結成分分解自体の意味は次の記事に書いた。 drken1…

2-SAT は強連結成分分解の典型的な応用例！ 問題へのリンク 問題概要 旗 を数直線上に設置したい。旗 は、座標 または座標 に設置可能である。 ただし、どの 2 つの旗も、その距離が 以上となるようにする必要がある。 本の旗を設置することが可能かどうかを…

まさに文字通り、強連結成分分解をしてください、という問題ですね。そしてこの問題は、Yosupo Judge の Strongly Connected Components が元になっているようです。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。 番目の辺は である。このグ…

最初誤読して、「何度でもスタート地点にワープして戻っても良い」というバージョンの問題を解いていた。 問題へのリンク editorial 問題概要 個の整数 と 2 以上の整数 が与えられる。 頂点からなる以下のような有向グラフであって、頂点 1 を始点として、…

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…