Ordenamiento Topológico
Dado un grafo dirigido con
v vértices y e aristas, se desea ordenar los vértices en un orden específico. Si existe una arista que va de v1 a v2, entonces el vértice de origen v1 debe aparecer antes en el arreglo de vértices que v2. De esta manera, tras ordenar los vértices, cada arista irá de un vértice con índice menor a otro con índice mayor.🤔
Observa que pueden existir distintos órdenes topológicos válidos.
Por otro lado, si el grafo contiene ciclos, no existe ningún orden topológico válido.
El algoritmo puede implementarse mediante un DFS que inicie desde cada vértice que aún no haya sido visitado. En cada llamada a DFS, primero se añaden recursivamente todos los nodos hijos del vértice actual y, solo cuando se hayan procesado todos los vértices hijos, se añade el vértice actual a la lista de respuesta. Esto garantiza que el vértice de origen aparezca después de todos los que son alcanzables desde él. Al terminar el algoritmo, invertiremos el orden de la lista de respuesta:
used = [False] * n # vértices utilizados
order = [] # orden topológico
def dfs(v): # dfs
used[v] = True # marcar el vértice como utilizado
for to in g[v]: # para cada vértice to adyacente a v
if not used[to]: # si to no está utilizado
dfs(to) # dfs desde to
order.append(v) # añadir v al orden topológico
for i in range(n): # para cada vértice
if not used[i]: # si el vértice no está utilizado
dfs(i) # dfs desde el vértice
print(*order[::-1]) # imprimir el orden topológicoDesafío: Organizar el Plan de Cursos
Se cuentan con
n cursos que se quieren tomar y hay un total de p prerrequisitos. Cada prerrequisito se representa como un par de cursos , lo que significa que se debe cursar antes de poder cursar (si el par es 1, 2, esto implica tomar el curso 2 antes que el curso 1).Se necesita verificar si es posible terminar todos los cursos.
Entrada
La primera línea de la entrada contiene dos enteros
n y p (1 ≤ n, p ≤ 10 000).Las siguientes
p líneas contienen pares de enteros (1 ≤ ≤ n).Salida
El programa debe imprimir
Yes si es posible tomar todos los cursos y No en caso contrario.Ejemplos
Entrada | Salida |
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