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

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

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