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

Envío 2544

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: d4vsanchez
  • Fecha: 2020-12-31 00:50:59 UTC (Hace casi 4 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.022 s 3 KBi
#2
Correcto
0.024 s 3 KBi
#3
Correcto
0.04 s 3 KBi
#4
Correcto
0.028 s 3 KBi
#5
Correcto
0.03 s 3 KBi
#6
Correcto
0.036 s 3 KBi
#7
Correcto
0.023 s 3 KBi
#8
Correcto
0.022 s 3 KBi
#9
Correcto
0.029 s 3 KBi
#10
Correcto
0.023 s 3 KBi
#11
Correcto
0.021 s 3 KBi
#12
Correcto
0.025 s 3 KBi
#13
Correcto
0.034 s 3 KBi
#14
Correcto
0.022 s 3 KBi
#15
Correcto
0.025 s 3 KBi
#16
Correcto
0.023 s 3 KBi
#17
Correcto
0.024 s 3 KBi
#18
Correcto
0.028 s 3 KBi
#19
Correcto
0.041 s 3 KBi
#20
Correcto
0.029 s 3 KBi
#21
Correcto
0.027 s 3 KBi
#22
Correcto
0.028 s 3 KBi
#23
Correcto
0.025 s 3 KBi
#24
Correcto
0.03 s 3 KBi
#25
Correcto
0.03 s 3 KBi
#26
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.194 s 125 KBi
#27
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.253 s 125 KBi
#28
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.207 s 125 KBi
#29
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.192 s 125 KBi
#30
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.247 s 125 KBi
#31
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.181 s 125 KBi
#32
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.185 s 125 KBi
#33
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.238 s 125 KBi
#34
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.244 s 125 KBi
#35
Error en tiempo de ejecución (NZEC) 
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/python-3.8.1/bin/python3 script.py
0.181 s 125 KBi
Puntos totales: 72 / 100

Código

def generate_graph_grid(size):
  grid = []
  for _ in range(size):
    grid.append([0] * size)
  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()