Module: clasificación topológica


Problem

1 /5


clasificación topológica

Theory Click to read/hide

El algoritmo se puede describir de la siguiente manera:
Dado un grafo dirigido con n vértices y m aristas. Se requiere renumerar sus vértices de tal manera que cada arista conduzca desde un vértice con un número más bajo a un vértice con uno más alto.
Es decir, se requiere encontrar una permutación de vértices (orden topológico) correspondiente al orden dado por todas las aristas del grafo.
Usaremos la búsqueda en profundidad (dfs(v))
Si agregamos nuestro vértice al comienzo de una lista al momento de salir de \(dfs(v)\) , entonces al final en esta lista obtienes una ordenación topológica.
Por lo tanto, la ordenación topológica deseada — esto se ordena en orden descendente de tiempos de salida.

Problem

Dado un grafo dirigido no ponderado. Es necesario ordenarlo topológicamente.

Entrada: La primera línea contiene dos números naturales n y m (1≤n≤105, 1≤m≤10< sup >5) — el número de vértices y aristas en el gráfico, respectivamente. Las siguientes m líneas enumeran los bordes del gráfico. Cada borde viene dado por un par de números — los números de los vértices inicial y final, respectivamente.
 
Salida: Imprime cualquier tipo topológico del gráfico como una secuencia de números de vértice. Si el gráfico no se puede ordenar topológicamente, imprima −1.
La primera línea contiene el número de vértices N y aristas M. 

Ejemplos
# Entrada Salida
1 4 4
14
4 3
4 2
3 2
1 4 3 2