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

Envío 4184

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: Serivt
  • Fecha: 2021-05-25 00:38:54 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.021 s 3 KBi
#2
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.022 s 3 KBi
#3
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.028 s 3 KBi
#4
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.021 s 3 KBi
#5
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.027 s 3 KBi
#6
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.033 s 3 KBi
#7
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.043 s 3 KBi
#8
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.022 s 3 KBi
#9
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.039 s 3 KBi
#10
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.028 s 3 KBi
#11
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.021 s 3 KBi
#12
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.021 s 3 KBi
#13
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.026 s 3 KBi
#14
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.022 s 4 KBi
#15
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.016 s 3 KBi
#16
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.022 s 3 KBi
#17
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.028 s 3 KBi
#18
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.027 s 3 KBi
#19
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.024 s 3 KBi
#20
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.024 s 3 KBi
#21
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.03 s 3 KBi
#22
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.022 s 3 KBi
#23
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.026 s 3 KBi
#24
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.026 s 3 KBi
#25
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.022 s 3 KBi
#26
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.023 s 3 KBi
#27
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.026 s 3 KBi
#28
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.028 s 3 KBi
#29
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.029 s 3 KBi
#30
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.02 s 3 KBi
#31
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.029 s 3 KBi
#32
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.033 s 3 KBi
#33
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.019 s 3 KBi
#34
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.016 s 3 KBi
#35
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 2, in <module>
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
ValueError: not allowed to raise maximum limit
0.024 s 3 KBi
Puntos totales: 0 / 100

Código

import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(10**6)

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) 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")