我们现在要解决一个问题，就如标题所说，我们要判断一个DAG的拓扑序是否唯一。

以下说两种做法。

做法1（推荐）

在拓扑排序时，我们只要每时每刻都判断一下，此时的队列大小是否大于 $1$ 即可。

因为，如果队列大小大于 $1$，则选择任何一个元素都可以加入到拓扑序的最后下标，所以拓扑序不唯一。

做法2

（以下是我考试时想出来的做法，思维难度较高，但整个构思过程中都没有思维跳跃）

1

首先，我们建出这个DAG，然后我们考虑，其实一个DAG唯一，有且仅当对于所有点对 $(u,v)$（$1 \leq u,v \leq n$），都满足以下两点之一：

  • 点 $u$ 可以到达点 $v$。
  • 点 $v$ 可以到达点 $u$。

此处证明一下。

其实，如果存在一个不满足上述条件的点对 $(u,v)$，那么整张图可能会张这样：（下面标记的 $(u,v)$ 只是其中一个）

在这种情况里，我们直接把红色集合和蓝色集合里的拓扑序“交换”，变成：

于是乎，就得到了另一个合法的拓扑序，证毕。

关于如果满足条件，则拓扑序唯一，此处不多赘述，自行脑补。

2

上述条件还可以继续变化，变成：

  • 对于所有点对 $(u,v)$（$1 \leq u,v \leq n$，且 $v$ 的拓扑序比 $u$ 的要大），都满足点 $u$ 可以到达点 $v$。

3

我们考虑定义函数 $f(x)$ 代表拓扑序为 $x$ 的节点，是否能到达所有拓扑序为 $y$（$x<y$）的点。

4

我们考虑求 $f(x)$，我们可以枚举拓扑序为 $x$ 的节点 $u$ 的所有出点 $v$（设其拓扑序为 $y$，且排除 $y \leq x$ 的所有点）。

然后，如果说 $f(y)$ 已经表示不可行了，输出无解。

否则，拓扑序为 $y \sim n$ 的点全部都可以被遍历到。

5

然后，我们求出 $y$ 的最小值 $y_{\min}$。

那么，我们可以直接遍历到拓扑序在 $y_{\min} \sim n$ 内的所有点。

所以，能遍历到 $x+1 \sim n$ 内的所有点，有且仅当 $y_{\min}$ 刚好等于 $x+1$，显然。

而这个条件，就相当于说存在一个当前 $u$ 的出点 $v$，其拓扑序刚好比 $u$ 的拓扑序要大 $1$。

6

有了这个条件，我们就可以直接判断了。

但还没完，我们要判断两点特殊情况：

  • 如果入度为 $0$ 的点超过 $1$ 个，拓扑序不唯一。
  • 如果出度为 $0$ 的点超过 $1$ 个，拓扑序不唯一。