Unikalna ścieżka na ukierunkowanym wykresie

Projektuję algorytm dla klasy, który określi, czy skierowany wykres jest unikalny w odniesieniu do wierzchołka $v$ tak, że dla każdego $u \ne v$ jest co najwyżej jedna ścieżka z $v$ do $u$. Zacząłem od użycia BFS (wyszukiwanie szerokości), aby znaleźć najkrótszą ścieżkę od v do innego wierzchołka u, a następnie ponownie uruchomiłem BFS, aby sprawdzić, czy można znaleźć alternatywną ścieżkę od v do u. Myślę jednak, że jest to zbyt czasochłonne. Czy ktoś ma jakieś wskazówki, jak znaleźć rozwiązanie przy krótszym czasie realizacji?

Użyj BFS, aby pracować wstecz od v, oznaczając każdy wierzchołek jako „odwiedzany” podczas pracy. Jeśli kiedykolwiek trafisz na wierzchołek, który wcześniej odwiedziłeś, twój wykres nie ma właściwości unikatowości. W przeciwnym razie tak jest.

Spójrz na algorytm Max Flow Min Cut .

Jest to prosta modyfikacja dowolnego przejścia przez wykres: jeśli znajdziesz krawędź do wcześniej zaznaczonego węzła, masz wiele ścieżek.