Определить, имеет ли направленный граф уникальное топологическое упорядочение?

Question

Я пытаюсь создать псевдокод для алгоритма, который сможет определить, имеет ли направленный граф уникальное топологическое упорядочение. Я уже придумал следующий псевдокод для топологической сортировки, но что мне нужно добавить или отредактировать, чтобы определить, имеет ли орграф уникальное топологическое упорядочение?

Input: A graph G 
Output: A list L that contain the sorted vertices 

define an empty list L; 
create a stack Stack; 
push all vertices with no incoming edges into Stack; 
while Stack is not empty do 

v ← Stack.pop(); 
add v to the list L; 

for all the vertices w with an edge e from v to w do 
remove edge e from G; 
if w has no other incoming edges then 
push w into Stack; 
if G has edges left then 
return error (graph G can’t be topological ordered); 
 else 
return L; 

Answer 1

Нет особой причины использовать стек, а не какой-либо другой коллекции. Если мы пэдем элементы недетерминированно, то мы можем реализовать все возможные топологические порядки. Таким образом, топологический порядок является уникальным тогда и только тогда, когда коллекция содержит один элемент каждый раз, когда мы выходим (кроме случаев, когда он пуст в конце).