█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 3649

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: jocarmp08
  • Fecha: 2021-04-04 20:39:30 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.029 s 3 KBi
#2
Correcto
0.019 s 3 KBi
#3
Correcto
0.03 s 3 KBi
#4
Correcto
0.019 s 3 KBi
#5
Correcto
0.033 s 4 KBi
#6
Correcto
0.028 s 3 KBi
#7
Correcto
0.026 s 3 KBi
#8
Correcto
0.019 s 3 KBi
#9
Correcto
0.042 s 4 KBi
#10
Correcto
0.03 s 3 KBi
#11
Correcto
0.019 s 3 KBi
#12
Correcto
0.027 s 3 KBi
#13
Correcto
0.033 s 3 KBi
#14
Correcto
0.026 s 3 KBi
#15
Correcto
0.024 s 3 KBi
#16
Correcto
0.037 s 8 KBi
#17
Correcto
0.028 s 3 KBi
#18
Correcto
0.033 s 3 KBi
#19
Correcto
0.027 s 3 KBi
#20
Correcto
0.042 s 7 KBi
#21
Correcto
0.033 s 8 KBi
#22
Correcto
0.025 s 3 KBi
#23
Correcto
0.027 s 3 KBi
#24
Correcto
0.036 s 3 KBi
#25
Correcto
0.027 s 3 KBi
#26
Correcto
0.042 s 3 KBi
#27
Correcto
0.413 s 7 KBi
#28
Correcto
0.029 s 3 KBi
#29
Correcto
0.402 s 7 KBi
#30
Correcto
0.028 s 3 KBi
#31
Correcto
0.066 s 4 KBi
#32
Correcto
0.353 s 7 KBi
#33
Correcto
0.075 s 6 KBi
#34
Correcto
0.125 s 6 KBi
#35
Correcto
0.334 s 7 KBi
Puntos totales: 100 / 100

Código

from collections import Counter, deque


def get_in_degree_vertices(graph):
    in_degree_vertices = Counter({key: 0 for key in graph.keys()})

    for neighbours in graph.values():
        for neighbour in neighbours:
            in_degree_vertices.update([neighbour])

    return in_degree_vertices


def graph_has_cycle(graph):
    in_degree_vertices = get_in_degree_vertices(graph)
    queue = deque(
        filter(lambda key: in_degree_vertices[key] == 0, in_degree_vertices.keys()))

    number_of_visited_vertices = 0
    while len(queue):
        vertex = queue.popleft()
        number_of_visited_vertices += 1
        neighbours = graph[vertex] if vertex in graph else []

        for neighbour in neighbours:
            in_degree_vertices.subtract([neighbour])

            if in_degree_vertices[neighbour] == 0:
                queue.append(neighbour)

    return number_of_visited_vertices < len(graph)


vertex_num, edge_num = [int(x) for x in input().split()]
result = False
if vertex_num and edge_num:
    adjacency_list = {}
    for _ in range(edge_num):
        from_vertex, to_vertex = [int(x) for x in input().split()]
        if from_vertex in adjacency_list:
            adjacency_list[from_vertex].append(to_vertex)
        else:
            adjacency_list[from_vertex] = [to_vertex]

    result = graph_has_cycle(adjacency_list)
print("Yes" if result else "No")