読者です 読者をやめる 読者になる 読者になる

トポロジカルソートの組合せを数え上げる

問題

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder

与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると1つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満たすかをチェック)の方法で部分点が取れる。

満点解法

以下のように動的計画法により解く。


公式解説 http://abc041.contest.atcoder.jp/data/abc/041/editorial.pdf

漸化式

トポロジカルソートする方法の通り数を考える。上記のスライドの例において頂点集合S = {1, 2, 3, 4, 5}と置く。トポロジカルソートにおいて最も右に置ける条件は出力辺を持たないノードである。Sの中でこの条件を満たすものは「5」である。f(S)を「Sをトポロジカルソートする方法の通り数」遠くと。f(S)は「5」を除いた頂点集合(S - {5})をトポロジカルソートした時の通り数と等しい。

Bit操作

頂点を含むか否かをBitを用いて表す。今回の解答は再帰処理を用いて行っている。よって始めの状態は「11111」からスタートする。 その状態から出力辺を持たないノードを順々に除いていく。これはbit操作ではフラグを削除する処理となる。 フラグを削除する操作は以下の通りだ。

出力辺の管理

今回はトポロジカルソートをがっくり行うというよりは、その性質を用いて数え上げるようにする。その時ポイントとなるのが各ノードの出力辺の管理だある。今回は配列outdegreeを用意しインデックスとノードを対応させ出力辺の数を管理した。

ソースコード