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

Envío 2543

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: d4vsanchez
  • Fecha: 2020-12-31 00:49:14 UTC (Hace casi 4 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.027 s 3 KBi
#2
Correcto
0.033 s 3 KBi
#3
Correcto
0.023 s 3 KBi
#4
Correcto
0.027 s 3 KBi
#5
Correcto
0.034 s 3 KBi
#6
Correcto
0.035 s 3 KBi
#7
Correcto
0.038 s 3 KBi
#8
Correcto
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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.039 s 3 KBi
#10
Correcto
0.025 s 3 KBi
#11
Correcto
0.026 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.023 s 3 KBi
#13
Correcto
0.023 s 3 KBi
#14
Correcto
0.028 s 3 KBi
#15
Correcto
0.036 s 3 KBi
#16
Correcto
0.027 s 3 KBi
#17
Correcto
0.024 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.034 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.028 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.027 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.023 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.026 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.033 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.029 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.032 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 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.046 s 4 KBi
#27
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.046 s 4 KBi
#28
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.029 s 4 KBi
#29
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.029 s 4 KBi
#30
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.031 s 4 KBi
#31
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.037 s 4 KBi
#32
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.029 s 4 KBi
#33
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.028 s 4 KBi
#34
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.03 s 4 KBi
#35
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 49, in <module>
    main()
  File "script.py", line 31, in main
    fill_graph_grid(graph_grid, source, target)
  File "script.py", line 8, in fill_graph_grid
    grid[source][target] =  1
IndexError: list assignment index out of range
0.034 s 4 KBi
Puntos totales: 43 / 100

Código

def generate_graph_grid(size):
  grid = []
  for _ in range(size):
    grid.append([0] * 5)
  return grid

def fill_graph_grid(grid, source, target):
  grid[source][target] =  1

def has_loops(graph_grid, i = 0, j = 0, visited = None):
  if visited is None:
    visited = []

  if i >= len(graph_grid) or j >= len(graph_grid):
    return False
  if i in visited:
    return True

  has_connection = graph_grid[i][j] == 1
  if has_connection:
    visited.append(i)
    return has_loops(graph_grid, j, 0, visited)
  return has_loops(graph_grid, i, j + 1, visited)

def main():
  nodes, connections = [int(x) for x in input().split()]
  graph_grid = generate_graph_grid(nodes)

  for _ in range(connections):
    source, target = [int(x) for x in input().split()]
    fill_graph_grid(graph_grid, source, target)

  i = 0
  j = 0
  looped = False

  while i < nodes and not looped:
    j = 0
    while j < nodes and not looped:
      looped = has_loops(graph_grid, i, j)
      j = j + 1
    i = i + 1

  if looped:
    print("Yes")
  else:
    print("No")

main()