takeg https://blog.hatena.ne.jp/takeg/ ベスパリブ https://takeg.hatenadiary.jp/ AtCoder 競技プログラミング 強連結成分分解（SCC） C++ 問題：advertisement - 宣伝 (Advertisement) 解説 「強連結成分分解（SCC）を使って同じグループの頂点を1つにまとめると、サイクルを含まないDAGになる」という性質を使う。 連絡先を知っている関係をグラフとして表す。 をSCCしたあと、グループを1つの頂点とみなす。 求める答えは、入次数が0の頂点（根と呼ぶことにする）の数。 もとのの入次数をindeg[i] := 頂点iの入次数とする。 SCCするとグループがわかるので、グループ内同士の有向辺を取り除いて入次数を減らし、グループ内のすべての頂点の入次数が0になれば、そのグループは根となる。 SCCのグループは1… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftakeg.hatenadiary.jp%2Fentry%2F2022%2F07%2F15%2F103105" title="Advertisement: 宣伝（日本情報オリンピック2009）の解説 - ベスパリブ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/t/takeg/20220715/20220715102024.png Hatena Blog https://hatena.blog 2022-07-15 10:31:05 rich https://takeg.hatenadiary.jp/entry/2022/07/15/103105 1.0 100%