morning_reading https://blog.hatena.ne.jp/morning_reading/ 毎朝30分読書会 https://morning-reading.hatenadiary.org/ 4-3 「グラフマスターへの道」からです。 強連結成分分解 強連結成分 = 有向グラフの頂点の部分集合で任意の2点が到達可能なもの 強連結成分を1ノードにまとめることで任意の有向グラフは DAG に変換できる Popular Cow - AがBを人気者と思っていてBがCを人気者と思っていたらAもCを人気者と思っている、というルールの元で示された"人気者と思ってるリスト"から全ての牛に人気者と思われている牛を数える 牛をノードに、"人気者と思っている"を有向辺として有向グラフと考えると、任意のノードから到達可能なノードがいくつかるかという問題 "自分以外の全員から人気者と思われている"集団は当然… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmorning-reading.hatenadiary.org%2Fentry%2F20110905%2Fp1" title="プログラミングコンテストチャレンジブック 4-3 その1 - 毎朝30分読書会" 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 2011-09-05 00:00:00 rich https://morning-reading.hatenadiary.org/entry/20110905/p1 1.0 100%