ŠIOM — Mažiausias topologinis rikiavimas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Mažiausias topologinis rikiavimas

Duotas kryptinis grafas, kurį sudaro $n$ viršūnių ir $m$ briaunų. Garantuota, kad jame nėra ciklų.

Reikia rasti šio grafo leksikografiškai mažiausią topologinį rikiavimą.

Sakoma, kad topologinis rikiavimas $a_1,a_2,...,a_n$ yra leksikografiškai mažesnis už topologinį rikiavimą $b_1,b_2,...,b_n$ , kai yra toks $i$ ( $1\\leqi\\leqn$ ), kuriam galioja:

visiems $j<i$ , galioja $a_j=b_j$ ;
$a_i<b_i$ .

Pavyzdžiui, seka $[2,5,4,8,1]$ yra leksikografiškai mažesnė už seką $[2,5,6,1,3]$ , nes pirmieji du nariai lygūs, o trečiasis mažesnis.

Įvestis

Pirmoje eilutėje pateikiami du natūralieji skaičiai $n$ ir $m$ ( $1\\leqn,m\\leq10^5$ ) - grafo viršūnių ir briaunų skaičius.

Toliau pateiktos $m$ eilučių, kur kiekvienoje jų yra po du skaičius $u$ ir $v$ ( $1\\lequ,v\\leqn$ ), reiškiančius, kad grafe yra briauna iš $u$ į $v$ .

Išvestis

Išveskite $n$ skaičių - leksikografiškai mažiausią topologinį rikiavimą.

Pavyzdžiai

Duomenys	Rezultatai	Paaiškinimai
6 5 2 3 1 4 2 6 3 5 6 5	1 2 3 4 6 5	Grafas atrodo taip: Keli kiti galimi topologiniai rikiavimai: - 2 3 6 5 1 4 - 1 2 4 6 3 5 - 1 4 2 3 6 5 Tačiau visi jie nėra topologiškai mažiausi, tad netinka.

Duomenys

Rezultatai

Paaiškinimai

1 2 3 4 6 5

Grafas atrodo taip: 

Keli kiti galimi topologiniai rikiavimai:
- 2 3 6 5 1 4
- 1 2 4 6 3 5
- 1 4 2 3 6 5
Tačiau visi jie nėra topologiškai mažiausi, tad netinka.

Šeštadieninė informatikos olimpiadininkų mokykla

Mažiausias topologinis rikiavimas

Įvestis

Išvestis

Pavyzdžiai