一般に、無向グラフ \(H\) 上の頂点 \(s\) から頂点 \(t\) への最短パスの個数は下記の手順で求められます。

• ステップ \(1\)：\(s\) から各頂点 \(v\) への距離 \(\mathrm{dist}[v]\) を幅優先探索によって求める。
• ステップ \(2\) : 「 \(s\) から \(t\) へのパスであって、パス上の全ての辺 \(u \rightarrow v\) が \(\mathrm{dist}[u] + 1 = \mathrm{dist}[v]\) を満たすもの」の本数を数える。 これは、\(s\) から各頂点 \(v\) への条件を満たすパスの本数 \(\mathrm{dp}[v]\) を、\(\mathrm{dist}[v]\) の昇順に求めていく動的計画法によって、\(\mathrm{dp}[t]\) として求められる。

ステップ \(1\) で頂点 \(t\) に到達できなかった場合は、\(s\) から \(t\) へのパスはないと判定できます。

以上を踏まえて、以下で本問題の解法を考えます。 対象となるグラフ \(G\) は \(N\) 頂点の完全グラフから、入力で指定された \(M\) 本の辺の通行が禁止されているグラフです。 \(G\) の通行可能な辺数は最大で \(\Theta(N^2)\) であるので、ステップ \(1\) とステップ \(2\) を愚直に行うのでは実行制限時間に間に合わせるのは絶望的です。 そこで、通行が禁止されている辺の本数は \(O(M)\) と少ないことに注目し、以下のような工夫をステップ \(1\) とステップ \(2\) のそれぞれに対して行います。

・ステップ \(1\) に対する工夫

通常の幅優先探索を行う際には 各頂点 \(v\) 対して「 \(v\) に隣接する未訪問の頂点全てを見つけ、それらを全て訪問済にする」という操作を行いますが、 この時に \(v\) に接続する通行可能な辺全てを調べる方法では、今回は最悪で \(\Theta(N^2)\) 時間かかってしまいます。 その対策として、幅優先探索の過程で現在未訪問の頂点の集合を \(L\) を保持しておき、頂点 \(v\) の隣接点を調べる際には、\(L\) に含まれる頂点のみを全て走査し、その中で辺 \(\lbrace v, u\rbrace\) が通行禁止でないような頂点 \(u\) 全てを訪問済にして \(L\) から削除すれば良いです。

辺 \(\lbrace v, u\rbrace\) が通行禁止かの判定は、例えば、通行禁止の辺 \(M\) 本を格納した平衡二分木等を用いて \(O(\log M)\) 時間で行うことができます。

\(v\) の隣接点の候補として \(L\) に含まれるある頂点 \(u\) を調べた結果として、

• 「辺 \(\lbrace v, u\rbrace\) は通行可能であり、頂点 \(u\) は未訪問から訪問済に変わる」、または、
• 「辺 \(\lbrace v, u\rbrace\) は通行禁止だった」

という出来事のどちらかが起こりますが、幅優先探索全体で前者は高々 \(N\) 回、後者は高々 \(M\) 回しか起こらないため、 ステップ \(1\) 全体を \(O((N+M) \log M)\) 時間で行うことができます。

・ステップ \(2\) に対する工夫

ステップ \(1\) で求めた距離 \(\mathrm{dist}[v]\) の昇順に \(\mathrm{dp}[v]\) を計算していきます。

本来のステップ \(2\) の手順に従えば、距離 \(d\) の頂点 \(v\) に対する \(\mathrm{dp}[v]\) を求めるには、 距離 \((d-1)\) の頂点 \(u\) のうち辺 \(\lbrace u, v\rbrace\) が通行可能なもの全てにわたる \(\mathrm{dp}[u]\) の和を取れば良いです。

しかし、\(v\) に接続する通行可能な辺全てを調べる方法では、最悪で \(\Theta(N^2)\) 時間かかります。 そこで代わりに、距離 \((d-1)\) の頂点全てにわたる \(\mathrm{dp}\) の和 \(\mathrm{sum}[d-1]\) から、「距離 \((d-1)\) の頂点 \(u\) で辺 \(\lbrace u, v\rbrace\) が通行禁止のもの」それぞれの \(\mathrm{dp}[u]\) を引くことで、\(\mathrm{dp}[v]\) を求めます。

そして、距離 \(d\) の頂点の \(\mathrm{dp}\) を全て求め終わるたびに、それらの和として \(\mathrm{sum}[d]\) を求めて、距離 \((d+1)\) の頂点の計算に進みます。

各頂点に接続する、通行禁止の辺のリストをあらかじめ保持しておくことで、上記の手順は全体で \(O(N + M)\) 時間で実行できます。