JOI '09 春合宿2:2- Advertisement 宣伝
問題
https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day2_21.pdf
解法
人を頂点として (a, b) に辺を張る.このとき,グラフ全体には木があったり,閉路があったり,閉路といくつかの辺・頂点が合体したものがあったりする.ここで,閉路を処理するのが面倒であり,1つの閉路を構成する頂点同士は互いに行き来できることを考えると,1つの閉路を1つの頂点のグループにしてしまいたいと考える.ここで,強連結成分分解を用いると,閉路をグループ化することが出来,トポロジカルソートした順序も得ることが出来る.後は,辺が入っていない頂点(グループ)から辺をたどっていけばよい.O(N + M).
解答
強連結成分分解をテンプレ化した.閉路を含む有向グラフを DAG にする有能なテクだと思った.