Module: Pesquise em profundidade. DFS


Problem

7 /12


classificação topológica

Theory Click to read/hide

O algoritmo pode ser descrito da seguinte forma:
Dado um grafo direcionado com n vértices e m arestas. É necessário renumerar seus vértices de forma que cada aresta conduza de um vértice com um número menor para um vértice com um número maior.
Em outras palavras, é necessário encontrar uma permutação de vértices (ordem topológica) correspondente à ordem dada por todas as arestas do grafo.
Usaremos a pesquisa em profundidade (dfs(v))
Se adicionarmos nosso vértice ao início de uma lista no momento da saída de \(dfs(v)\) , então no final nesta lista você obtém uma classificação topológica.
Assim, a ordenação topológica desejada — isso é classificado em ordem decrescente de horários de saída.

Problem

Dado um grafo direcionado não ponderado. É necessário ordená-lo topologicamente.

Entrada: A primeira linha contém dois números naturais n e m (1≤n≤105, 1≤m≤10< sup >5) — o número de vértices e arestas no grafo, respectivamente. As próximas m linhas listam as arestas do gráfico. Cada aresta é dada por um par de números — os números dos vértices inicial e final, respectivamente.
 
Saída: Imprima qualquer classificação topológica do gráfico como uma sequência de números de vértice. Se o gráfico não puder ser classificado topologicamente, imprima −1.
A primeira linha contém o número de vértices N e arestas M. 

Exemplos
# Entrada Saída
1 4 4
14
4 3
4 2
3 2		 1 4 3 2

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!