2021/8/5
・強連結成分分解(SCC)をする。
強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語
->まず、どこからでもいいので深さ優先探索をして帰りがけ順に頂点番号を保持する。
頂点番号を逆順にしてから、再び深さ優先探索をして、詰まったところでグループ分けができる。この問題では、そこで行き来できるパスの総数を求めたいのでそのグループでは、1/2 * ai * (ai-1)でそれぞれのグループのパスの総数を数えることができる。
(xからy, yからxのパスがある->ループ)
・最大公約数を使う
・パリティを考える