Ordenação Topológica
Dado um grafo direcionado com
v vértices e e arestas, você deseja ordenar os vértices numa certa sequência. Se existir uma aresta indo de v1 para v2, o vértice de origem v1 deve aparecer antes na lista de vértices do que v2. Assim, após a ordenação, cada aresta partirá de um vértice com índice menor em direção a um vértice com índice maior.🤔
Note que podem existir várias ordens topológicas válidas.
Por outro lado, se o grafo contiver ciclos, não haverá nenhuma ordem topológica válida.
O algoritmo pode ser implementado com uma DFS que parte de cada vértice não visitado ainda. Em cada chamada de DFS, adicionamos recursivamente todos os nós filhos do vértice atual e, somente depois que todos esses nós forem processados, adicionamos o vértice atual à lista de resultados. Isso garante que o vértice de origem apareça mais tarde do que todos os que podem ser alcançados a partir dele. Ao final do algoritmo, a lista de resultados é invertida:
used = [False] * n # vértices usados
order = [] # ordem topológica
def dfs(v): # DFS
used[v] = True # marca o vértice como usado
for to in g[v]: # para cada vértice 'to' adjacente a v
if not used[to]: # se 'to' não estiver usado
dfs(to) # faz DFS a partir de 'to'
order.append(v) # adiciona v à ordem topológica
for i in range(n): # para cada vértice
if not used[i]: # se o vértice não estiver usado
dfs(i) # faz DFS a partir do vértice
print(*order[::-1]) # imprime a ordem topológicaDesafio: Organizar o Cronograma de Cursos
Você tem
n cursos que gostaria de fazer e, ao todo, há p pré-requisitos. Cada pré-requisito representa um par de cursos , significando que você deve cursar antes de . (Por exemplo, se o par for (1, 2), é necessário fazer o curso 2 antes de começar o curso 1).É preciso verificar se é possível concluir todos os cursos.
Entrada
A primeira linha da entrada contém dois inteiros
n e p (1 ≤ n, p ≤ 10 000).As próximas
p linhas contêm pares de inteiros (1 ≤ ≤ n).Saída
O programa deve imprimir
Yes caso seja possível completar todos os cursos e No caso contrário.Exemplos
Entrada | Saída |
2 1
2 1 | Yes |
2 2
2 1
1 2 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB