Consider a graph \(G\) with vertices \(1,\ldots,N\) and directed edges from \(X_i\) to \(Y_i\). For any topological order \(P\), the sequence \(A\) such that \(A_{P_i}=i\) satisfies the condition by definition of topological order. The converse also holds. Therefore, \(A\) is unique if and only if the topological order of \(G\) is unique.

The topological order of \(G\) is unique if and only if, in the course of actual topological sorting, the next vertex to choose (those with indegrees \(0\)) is always unique, which can be checked easily.

Writer’s solution (C++)

Also, the topological order is unique if and only if the longest path in \(G\) is \((N-1)\), so we can use this fact to solve this problem.

Writer’s solution (C++)