RT。

命题

在 DAG $G=(V,E)$ 里，设编号最小的节点为 $x$。

我们称所有 $x$ 可达的节点之集为 $S$（不含 $x$）。

称所有 $x$ 不可达的节点之集为 $T$（不含 $x$）。

显然，$S+T+\{x\}=V$。

我们有：$G$ 的字典序最大的拓扑序由三部分顺次拼接而成，它们依次是，$T$ 的字典序最大的拓扑序， $x$，和 $S$ 的字典序最大的拓扑序。

证明

显然，$x$ 应待在倒数第 $|S|+1$ 位。

反证法证明：假设 $x$ 待在倒数第 $|S|+1$ 位之前，那么 $x$ 之后定有一个节点属于 $T$，不妨设其为 $y$。

我们令 $Pos(i)$ 表示节点 $i$ 的位置。

我们将节点 $y$ 移至 $Pos(x)$，并将 $Pos(x)\sim Pos(y)-1$ 的节点统一后移一位。

仍满足拓扑序性质。

字典序更小了。

与假设矛盾，命题成立。

证毕。

问题

一、命题是否正确。

二、证明是否严谨、准确。

三、能否根据该引理，得到一种线性的，能求 $G$ 的字典序最大的拓扑序的算法。