tsukuno https://blog.hatena.ne.jp/tsukuno/ なんとなくな日々のコメント https://tsukuno.hatenadiary.org/ 読書 2章付近 クロスフリーとかラミナーとか後の方で使うっぽい話がされているけど、良く分からないので保留。木構造で表現できるのがクロスフリーで、DAGっぽくなるとクロスしちゃってるってことなんだろう、多分。(くらいのいい加減な認識。) 強連結成分の取得アルゴリズムについて。無向グラフなら辺があれば行って戻れるので、BFSなりDFSなりをすればすぐに取得できる。有向グラフについては、探索しても行けることしか分からないので、戻れることを別途調べないとダメ。戻れることを調べるには、辺の向きを逆向きにして探索する必要がある。 全部のノードについて、行って戻れる点を調べればいいが、それだと重たいので、強連結成… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftsukuno.hatenadiary.org%2Fentry%2F20101228%2F1293518085" title=" 組合せ最適化 - なんとなくな日々のコメント" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-12-28 15:34:45 rich https://tsukuno.hatenadiary.org/entry/20101228/1293518085 1.0 100%