Jalur unik dalam grafik terarah

Saya merancang sebuah algoritma untuk kelas yang akan menentukan apakah grafik yang diarahkan adalah unik sehubungan dengan vertex sehingga untuk setiap u ≠ v ada paling banyak satu jalur dari v ke u . Saya sudah mulai dengan menggunakan BFS (pencarian luas-pertama) untuk menemukan jalur terpendek dari v ke simpul lain u, dan kemudian menjalankan BFS lagi untuk melihat apakah jalur alternatif dapat ditemukan dari v ke u. Saya pikir ini terlalu memakan waktu. Adakah yang punya petunjuk tentang bagaimana solusinya dapat ditemukan dengan waktu eksekusi yang lebih singkat?$v$$u \ne v$$v$$u$

Gunakan BFS untuk bekerja mundur dari v, menandai setiap simpul sebagai 'dikunjungi' saat Anda pergi. Jika Anda pernah menekan titik yang sebelumnya Anda kunjungi, grafik Anda tidak memiliki properti keunikan. Kalau tidak, itu akan terjadi.

Lihatlah algoritma Max Flow Min Cut .

Ini adalah modifikasi sederhana dari setiap grafik traversal: jika Anda menemukan tepi ke simpul yang sebelumnya ditandai, maka Anda memiliki beberapa jalur.