トポロジカルソートの組合せを数え上げる
問題
D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると１つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満たすかをチェック)の方法で部分点が取れる。
満点解法
以下のように動的計画法により解く。
公式解説 http://abc041.contest.atcoder.jp/data/abc/041/editorial.pdf
漸化式
トポロジカルソートする方法の通り数を考える。上記のスライドの例において頂点集合S = {1, 2, 3, 4, 5}と置く。トポロジカルソートにおいて最も右に置ける条件は出力辺を持たないノードである。Sの中でこの条件を満たすものは「５」である。f(S)を「Sをトポロジカルソートする方法の通り数」遠くと。f(S)は「5」を除いた頂点集合(S - {5})をトポロジカルソートした時の通り数と等しい。
Bit操作
頂点を含むか否かをBitを用いて表す。今回の解答は再帰処理を用いて行っている。よって始めの状態は「11111」からスタートする。 その状態から出力辺を持たないノードを順々に除いていく。これはbit操作ではフラグを削除する処理となる。 フラグを削除する操作は以下の通りだ。
出力辺の管理
今回はトポロジカルソートをがっくり行うというよりは、その性質を用いて数え上げるようにする。その時ポイントとなるのが各ノードの出力辺の管理だある。今回は配列outdegreeを用意しインデックスとノードを対応させ出力辺の数を管理した。
