\(1,\ldots,N\) を頂点とし、\(X_i\) から \(Y_i\) へ有向辺をもつグラフ \(G\) を考えます。\(G\) の任意のトポロジカル順序 \(P\) について、\(A_{P_i}=i\) と定めた数列 \(A\) はトポロジカル順序の定義より条件を満たします。逆も成り立ちます。したがって、\(G\) のトポロジカル順序が一意であることが、\(A\) が一意であることの必要十分条件です。

トポロジカル順序が一意であることは、実際にトポロジカルソートを行うアルゴリズムにおいて、どのタイミングにおいても次に選ぶ頂点(入次数が \(0\) の頂点)が一意であることが必要十分です。この条件は容易に確かめられます。

Writer解(C++)

この他、トポロジカル順序が一意であることは、\(G\) の最長パスの長さが \(N-1\) であることとも同値であるため、これにより判定することもできます。

Writer解(C++)