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

Envío 3646

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: jocarmp08
  • Fecha: 2021-04-04 19:47:01 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.026 s 3 KBi
#2
Correcto
0.037 s 3 KBi
#3
Correcto
0.031 s 3 KBi
#4
Correcto
0.024 s 3 KBi
#5
Correcto
0.032 s 3 KBi
#6
Correcto
0.029 s 3 KBi
#7
Correcto
0.019 s 3 KBi
#8
Correcto
0.028 s 3 KBi
#9
Correcto
0.035 s 3 KBi
#10
Correcto
0.025 s 3 KBi
#11
Correcto
0.039 s 3 KBi
#12
Correcto
0.03 s 3 KBi
#13
Correcto
0.028 s 3 KBi
#14
Incorrecto
0.027 s 3 KBi
#15
Correcto
0.026 s 3 KBi
#16
Correcto
0.026 s 3 KBi
#17
Correcto
0.033 s 3 KBi
#18
Incorrecto
0.038 s 3 KBi
#19
Incorrecto
0.027 s 3 KBi
#20
Incorrecto
0.029 s 3 KBi
#21
Correcto
0.034 s 3 KBi
#22
Incorrecto
0.02 s 3 KBi
#23
Incorrecto
0.029 s 3 KBi
#24
Correcto
0.032 s 3 KBi
#25
Correcto
0.019 s 3 KBi
#26
Incorrecto
0.028 s 3 KBi
#27
Incorrecto
0.39 s 7 KBi
#28
Incorrecto
0.028 s 3 KBi
#29
Incorrecto
0.38 s 7 KBi
#30
Incorrecto
0.035 s 3 KBi
#31
Incorrecto
0.092 s 4 KBi
#32
Correcto
0.293 s 7 KBi
#33
Correcto
0.125 s 6 KBi
#34
Correcto
0.114 s 5 KBi
#35
Correcto
0.21 s 7 KBi
Puntos totales: 66 / 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 vertex in graph:
        for neighbour in graph[vertex]:
            in_degree_vertices.update([neighbour])

    return in_degree_vertices


def graph_has_cycle(graph, vertex_num):
    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 < vertex_num


vertex_num, edge_num = [int(x) for x in input().split()]
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 = False if edge_num == 0 else graph_has_cycle(
    adjacency_list, vertex_num)
print("Yes" if result else "No")