Chemin unique dans un graphique dirigé

Je conçois un algorithme pour une classe qui déterminera si un graphe orienté est unique par rapport à un sommet telle sorte que pour tout il y ait au plus un chemin de à . J'ai commencé par utiliser BFS (recherche en largeur) pour trouver le chemin le plus court de v à un autre sommet u, puis réexécuter BFS pour voir si un chemin alternatif peut être trouvé de v à u. Je pense cependant que cela prend trop de temps. Quelqu'un a-t-il des conseils sur la façon de trouver la solution avec un temps d'exécution plus court?$v$$u \ne v$$v$$u$

Utilisez BFS pour travailler en arrière à partir de v, en marquant chaque sommet comme étant `` visité '' au fur et à mesure. Si vous avez déjà atteint un sommet que vous avez déjà visité, votre graphique n'a pas la propriété d'unicité. Sinon, c'est le cas.

Regardez l' algorithme Max Flow Min Cut .

C'est une simple modification de toute traversée de graphe: si vous trouvez une arête à un nœud précédemment marqué, vous avez plusieurs chemins.