ARC 030 : 有向グラフ

グラフ

問題↓


C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder

解けませんでした。

ので解いた。

問題概要

  • 有向グラフがあります。
  • 各頂点には一文字のアルファベットが書いてあります。
  • 任意の頂点から頂点をたどっていって、K文字からなる文字列を作りたいです。
  • ある頂点にいる時に必ずしもその文字を取る必要きはありません。
  • 文字をある頂点から取るとその頂点からは文字を取ることはできません。

解法

  • 閉路になってるとこを併合するとDAGになるのでDP
  • 閉路を一纏めにするにはワーシャルフロイドを使用すると楽
  • 強連結性分解じゃなかった
ソースコード

感想

強連結成分解が想定回らしいが謎。

そもそも強連結成分分解を理解してませんでした。

任意の２点間に双方向の辺が存在するような頂点集合にまとめることを強連結成分分解だと思っていたら実は任意の二点間に対して双方向にパスが存在するような頂点集合だった。

つまり上記の解法でやりたいことと一緒。ワーシャルフロイドでもできるが、Nがでかいと死ぬ。

つまりやっぱり、強連結成分分解が想定解。

強連結成分分解で解いたコード

そこそこ綺麗に書けた（のかなぁ）

実際ワーシャルフロイドをアリ本のO(V+E)のやつに変えただけなのでなんとも言えないが、こっちのほうがDAGに直す時の処理が綺麗にかける感じがする。

強連結成分分解自体のコードは簡単なので何も見ないでも書けそう。

というか、この問題文字列のdpの部分が一番バグりやすいと思う。