问题描述
\(i\ 的拓扑序 \(\in [l_i,r_i]\。
题解
\(u\，令 \(\forall (v,u\in E, l_u\leftarrow \max(l_u,l_v+1,\forall (u,v\in E, r_u\leftarrow \min(r_u,r_v-1\。
\(l_u\ 对任何可能的拓扑序的最小值取 \(\max\，\(r_u\ 同理。若此时有节点 \(l_u>r_u\ 则无解。
\(r\ 端点排序，然后以 \(l\ 端点为关键字插入大根堆中。从大到小依次考虑拓扑序 \(i\ 应为哪个节点，将所有 \(r_u\ge i\ 的节点插入堆中，然后取出 \(l_u\ 最大的，若 \(l_u>i\ 则显然无解，否则直接令 \(topo_i=u\，弹堆。由贪心交换性质应该可以证明这是可能的最优情况，如果这样都无解那么一定无解。至于正确性，我们发现如果当前存在 \(j>i\ 使得 \((topo_j,topo_i\in E\，则会有 \(l_{topo[i]}>l_{topo[j]}\，与每次取出 \(l\ 最大的区间矛盾。