Envío 3643
Problema 0x53 - Encontrar ciclos en un grafo dirigido
- Autor: jocarmp08
- Fecha: 2021-04-04 18:17:36 UTC (Hace casi 4 años)
| Caso # | Resultado | Tiempo | Memoria |
|---|---|---|---|
| #1 |
Correcto
|
0.026 s | 3 KBi |
| #2 |
Correcto
|
0.028 s | 3 KBi |
| #3 |
Correcto
|
0.026 s | 3 KBi |
| #4 |
Correcto
|
0.027 s | 3 KBi |
| #5 |
Correcto
|
0.03 s | 3 KBi |
| #6 |
Correcto
|
0.025 s | 3 KBi |
| #7 |
Correcto
|
0.021 s | 3 KBi |
| #8 |
Correcto
|
0.024 s | 3 KBi |
| #9 |
Correcto
|
0.021 s | 3 KBi |
| #10 |
Correcto
|
0.021 s | 3 KBi |
| #11 |
Correcto
|
0.027 s | 3 KBi |
| #12 |
Correcto
|
0.027 s | 4 KBi |
| #13 |
Correcto
|
0.036 s | 7 KBi |
| #14 |
Correcto
|
0.021 s | 3 KBi |
| #15 |
Correcto
|
0.021 s | 3 KBi |
| #16 |
Correcto
|
0.029 s | 3 KBi |
| #17 |
Correcto
|
0.027 s | 3 KBi |
| #18 |
Correcto
|
0.021 s | 3 KBi |
| #19 |
Correcto
|
0.022 s | 3 KBi |
| #20 |
Correcto
|
0.023 s | 3 KBi |
| #21 |
Correcto
|
0.021 s | 3 KBi |
| #22 |
Correcto
|
0.025 s | 3 KBi |
| #23 |
Correcto
|
0.023 s | 3 KBi |
| #24 |
Correcto
|
0.023 s | 3 KBi |
| #25 |
Correcto
|
0.027 s | 6 KBi |
| #26 |
Correcto
|
0.021 s | 3 KBi |
| #27 |
Correcto
|
0.228 s | 7 KBi |
| #28 |
Correcto
|
0.017 s | 3 KBi |
| #29 |
Correcto
|
0.233 s | 7 KBi |
| #30 |
Correcto
|
0.02 s | 3 KBi |
| #31 |
Correcto
|
0.052 s | 4 KBi |
| #32 |
Correcto
|
0.274 s | 6 KBi |
| #33 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 42, in <module>
print("Yes" if graph_has_cycle(adjacency_list) else "No")
File "script.py", line 25, in graph_has_cycle
has_cycle = vertex_has_cycle(vertex, graph, path, visited_vertex)
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
[Previous line repeated 994 more times]
File "script.py", line 2, in vertex_has_cycle
visited.add(vertex)
RecursionError: maximum recursion depth exceeded while calling a Python object
|
0.066 s | 6 KBi |
| #34 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 42, in <module>
print("Yes" if graph_has_cycle(adjacency_list) else "No")
File "script.py", line 25, in graph_has_cycle
has_cycle = vertex_has_cycle(vertex, graph, path, visited_vertex)
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
[Previous line repeated 994 more times]
File "script.py", line 2, in vertex_has_cycle
visited.add(vertex)
RecursionError: maximum recursion depth exceeded while calling a Python object
|
0.057 s | 6 KBi |
| #35 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 42, in <module>
print("Yes" if graph_has_cycle(adjacency_list) else "No")
File "script.py", line 25, in graph_has_cycle
has_cycle = vertex_has_cycle(vertex, graph, path, visited_vertex)
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
File "script.py", line 10, in vertex_has_cycle
has_cycle = vertex_has_cycle(
[Previous line repeated 994 more times]
File "script.py", line 2, in vertex_has_cycle
visited.add(vertex)
RecursionError: maximum recursion depth exceeded while calling a Python object
|
0.237 s | 7 KBi |
Puntos totales: 92 / 100
Código
def vertex_has_cycle(vertex, graph, path, visited):
visited.add(vertex)
neighbours = graph[vertex] if vertex in graph else []
for neighbour in neighbours:
if neighbour in path:
return True
elif neighbour not in visited:
path.add(neighbour)
has_cycle = vertex_has_cycle(
neighbour, graph, path, visited)
if has_cycle:
return True
path.remove(vertex)
return False
def graph_has_cycle(graph):
visited_vertex = set()
for vertex in graph:
if vertex not in visited_vertex:
path = set()
path.add(vertex)
has_cycle = vertex_has_cycle(vertex, graph, path, visited_vertex)
if has_cycle:
return True
return False
vertex_num, edge_num = [int(x) for x in input().split()]
adjacency_list = {}
for _ in range(edge_num):
from_vertex, to_vertex = [int(x) for x in input().split()]
if from_vertex in adjacency_list:
adjacency_list[from_vertex].append(to_vertex)
else:
adjacency_list[from_vertex] = [to_vertex]
print("Yes" if graph_has_cycle(adjacency_list) else "No")