Envío 4179

Problema 0x53 - Encontrar ciclos en un grafo dirigido

Autor: Serivt
Fecha: 2021-05-25 00:14:07 UTC (Hace casi 3 años)

Caso #	Resultado	Tiempo	Memoria
#1	Correcto	0.024 s	3 KBi
#2	Correcto	0.02 s	3 KBi
#3	Correcto	0.022 s	3 KBi
#4	Correcto	0.023 s	5 KBi
#5	Correcto	0.022 s	3 KBi
#6	Correcto	0.029 s	3 KBi
#7	Correcto	0.021 s	3 KBi
#8	Correcto	0.022 s	3 KBi
#9	Correcto	0.043 s	3 KBi
#10	Correcto	0.043 s	3 KBi
#11	Correcto	0.023 s	3 KBi
#12	Correcto	0.021 s	3 KBi
#13	Correcto	0.022 s	3 KBi
#14	Correcto	0.027 s	3 KBi
#15	Correcto	0.04 s	5 KBi
#16	Correcto	0.034 s	3 KBi
#17	Correcto	0.02 s	3 KBi
#18	Correcto	0.022 s	5 KBi
#19	Correcto	0.026 s	3 KBi
#20	Correcto	0.022 s	3 KBi
#21	Correcto	0.022 s	4 KBi
#22	Correcto	0.022 s	3 KBi
#23	Correcto	0.027 s	3 KBi
#24	Correcto	0.022 s	3 KBi
#25	Correcto	0.021 s	3 KBi
#26	Correcto	0.046 s	13 KBi
#27	Correcto	0.257 s	13 KBi
#28	Correcto	0.042 s	8 KBi
#29	Correcto	0.253 s	12 KBi
#30	Correcto	0.078 s	8 KBi
#31	Correcto	0.063 s	8 KBi
#32	Correcto	0.436 s	13 KBi
#33	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 37, in <module> print("Yes" if hasCycles() else "No") File "script.py", line 20, in hasCycles if node["visited"] is False and dfs(node): File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: [Previous line repeated 994 more times] File "script.py", line 11, in dfs edge = graph[edge] RecursionError: maximum recursion depth exceeded in comparison	0.077 s	9 KBi
#34	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 37, in <module> print("Yes" if hasCycles() else "No") File "script.py", line 20, in hasCycles if node["visited"] is False and dfs(node): File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: [Previous line repeated 994 more times] File "script.py", line 11, in dfs edge = graph[edge] RecursionError: maximum recursion depth exceeded in comparison	0.069 s	9 KBi
#35	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 37, in <module> print("Yes" if hasCycles() else "No") File "script.py", line 20, in hasCycles if node["visited"] is False and dfs(node): File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: File "script.py", line 12, in dfs if edge["visited"] is False and dfs(edge) is True: [Previous line repeated 994 more times] File "script.py", line 11, in dfs edge = graph[edge] RecursionError: maximum recursion depth exceeded in comparison	0.345 s	9 KBi

Puntos totales: 92 / 100

Código

graph = {}

# Depth First Search
def dfs(node):
    if node["visited"] is True:
        return False
    if node["explore"] is True:
        return True
    node["explore"] = True
    for edge in node["edges"]:
        edge = graph[edge]
        if edge["visited"] is False and dfs(edge) is True:
            return True
    node["explore"] = False
    node["visited"] = True
    return False

def hasCycles():
    for node in graph.values():
        if node["visited"] is False and dfs(node):
            return True
    return False

n, m = [int(x) for x in input().split()]

for i in range(n):
    graph[i] = {
        "edges": set(),
        "visited": False,
        "explore": False
    }

for i in range(m):
    u, v = [int(x) for x in input().split()]
    graph[u]["edges"].add(v)

print("Yes" if hasCycles() else "No")