拓扑序列唯一吗?
比较模板的topological-sort题,关键在于每个元素都严格存在唯一的大小关系,而一般的拓扑排序只给出一个可能解,这就需要每趟排序的过程中监视它是不是总坚持一条唯一的路径。
算法导论里面的拓扑排序运用的是DFS the DAG,记录每个顶点的进入时间和离开时间,根据其先后插入单链表的做法。而我认为一种方法是更直观的,就是维护一个入度为0的顶点集合(我用的队列其实没差),每次对其中一个加入结果序列——同时删除它的所有出边——更新其他点的入度的做法,在判断拓扑排序结果唯一性时这种方法也表现出了一个优势,每次访问0入度集合时查看大小,当元素多于1的时候可行的选择就出现了分歧——即可判定此DAG的拓扑排序不唯一。