Module: Cari secara mendalam. DFS


Problem

7 /12


Isihan topologi

Theory Click to read/hide

Algoritma boleh diterangkan seperti berikut:
Diberi graf berarah dengan n bucu dan m tepi. Ia dikehendaki menomborkan semula bucunya sedemikian rupa sehingga setiap tepi mengarah dari bucu dengan nombor yang lebih rendah ke bucu dengan yang lebih tinggi.
Dalam erti kata lain, ia diperlukan untuk mencari pilih atur bucu (tertib topologi) yang sepadan dengan susunan yang diberikan oleh semua tepi graf.
Kami akan menggunakan carian depth-first (dfs(v))
Jika kami menambah bucu kami pada permulaan senarai pada masa keluar dari \(dfs(v)\) , maka pada akhirnya dalam senarai ini anda mendapat jenis topologi.
Oleh itu, isihan topologi yang diingini — ini diisih mengikut tertib menurun masa keluar.

Problem

Diberi graf tidak berwajaran terarah. Perlu mengisihnya secara topologi.

Input: Baris pertama mengandungi dua nombor asli n dan m (1≤n≤105, 1≤m≤10< sup >5) — bilangan bucu dan tepi dalam graf, masing-masing. M baris seterusnya menyenaraikan tepi graf. Setiap tepi diberikan oleh sepasang nombor — nombor bucu mula dan tamat, masing-masing.
 
Output: Cetak sebarang jenis topologi graf sebagai jujukan nombor bucu. Jika graf tidak boleh diisih secara topologi, cetak &tolak;1.
Baris pertama mengandungi bilangan bucu N dan tepi M. 

Contoh
# Input Output
1 4 4
14
4 3
4 2
3 2
1 4 3 2