グラフを使った言い換え

各成分が \(0,1\) である \(N\) 次正方行列 \(A\) に対応する、 \((R_1,\dots,R_N), (C_1,\dots,C_N)\) を頂点とした完全二部グラフに以下のように向きをつけた有向グラフを考えます。

• \(A_{i,j}=1\) であるとき、\(R_i\) から \(C_j\) にむかって向きをつける
• \(A_{i,j}=0\) であるとき、\(C_j\) から \(R_i\) にむかって向きをつける

さらに、\(2\) つのグラフで、それぞれ頂点のについて、入次数と出次数がそれぞれ等しいとき、グラフが似ていると定義します。また、あるグラフのある辺が固定されていることを、それと似ている任意のグラフ上でその辺が（同じ向きで）存在していることと定義します。

このような \(K_{N,N}\) に向きをつけた有向グラフと、各成分が \(0,1\) である \(N\) 次正方行列は一対一対応していて、\(i\) 行 \(j\) 列成分が固定されていることは、対応するグラフの \(R_i\) と \(C_j\) を（どちらかの方向に）結ぶ辺が固定されていることと同値です。以上でこの問題を有向グラフで言い換えられたので、今後このグラフ上で考察を進めることにします。

解法

似ている \(2\) つのグラフを用意し、向きが同じ辺をすべて消したときに残るグラフを考えます。グラフが似ていることの定義から、残ったグラフのそれぞれの頂点について、入次数は出次数と等しいです。つまり、残ったグラフはいくつかのサイクルのあつまりです。逆に、あるグラフについて、あるサイクルに含まれる辺の向きをすべて逆にしたグラフは、元のグラフと似ています。

よって、辺が固定されていないことの必要十分条件は、その辺がサイクルに含まれることです。以下の値の組み合わせがありうるかどうかを求める動的計画法をすると、\(O(N^6)\) で解けます（定数倍が重い場合、手元ですべての場合を求めて答えを埋め込むこともできます）。

• \((R_1,\dots,R_N)\) のうち既に強連結成分に割り当て済みの頂点の数
• \( (C_1,\dots,C_N)\) のうち既に強連結成分に割り当て済みの頂点の数
• 強連結成分に含まれる（つまり、固定されていない）辺の数

二部性から、強連結成分を作るときは \((R_1,\dots,R_N)\) と \( (C_1,\dots,C_N)\) のそれぞれから \(2\) 頂点以上選ぶ必要があることに注意してください。逆に、両側に \(2\) 頂点以上あれば必ず強連結にできます。

C++による実装例