Envío 4183

Problema 0x53 - Encontrar ciclos en un grafo dirigido

Autor: Serivt
Fecha: 2021-05-25 00:36:06 UTC (Hace más de 3 años)

Caso #	Resultado	Tiempo	Memoria
#1	Correcto	0.022 s	3 KBi
#2	Correcto	0.019 s	3 KBi
#3	Correcto	0.036 s	3 KBi
#4	Correcto	0.016 s	3 KBi
#5	Correcto	0.023 s	3 KBi
#6	Correcto	0.02 s	3 KBi
#7	Correcto	0.024 s	3 KBi
#8	Correcto	0.03 s	3 KBi
#9	Correcto	0.02 s	3 KBi
#10	Correcto	0.02 s	3 KBi
#11	Correcto	0.021 s	3 KBi
#12	Correcto	0.023 s	3 KBi
#13	Correcto	0.031 s	3 KBi
#14	Correcto	0.022 s	3 KBi
#15	Correcto	0.033 s	3 KBi
#16	Correcto	0.031 s	3 KBi
#17	Correcto	0.021 s	3 KBi
#18	Correcto	0.021 s	3 KBi
#19	Correcto	0.021 s	3 KBi
#20	Correcto	0.02 s	3 KBi
#21	Correcto	0.024 s	3 KBi
#22	Correcto	0.021 s	3 KBi
#23	Correcto	0.019 s	3 KBi
#24	Correcto	0.022 s	3 KBi
#25	Correcto	0.023 s	3 KBi
#26	Correcto	0.052 s	8 KBi
#27	Correcto	0.251 s	13 KBi
#28	Correcto	0.042 s	8 KBi
#29	Correcto	0.368 s	13 KBi
#30	Correcto	0.087 s	8 KBi
#31	Correcto	0.105 s	8 KBi
#32	Correcto	0.184 s	12 KBi
#33	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 39, in <module> print("Yes" if hasCycles() else "No") File "script.py", line 22, in hasCycles if node["visited"] is False and dfs(node) 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: 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.12 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 39, in <module> print("Yes" if hasCycles() else "No") File "script.py", line 22, in hasCycles if node["visited"] is False and dfs(node) 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: 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.072 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 39, in <module> print("Yes" if hasCycles() else "No") File "script.py", line 22, in hasCycles if node["visited"] is False and dfs(node) 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: 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.206 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
        elif edge["explore"] 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) is True:
            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")