Submit Info #41383

Problem Lang User Status Time Memory
Cycle Detection pypy3 masaaa AC 1868 ms 157.34 MiB

ケース詳細
Name Status Time Memory
example_00 AC 52 ms 29.79 MiB
example_01 AC 50 ms 29.84 MiB
example_02 AC 51 ms 29.83 MiB
random_00 AC 776 ms 145.71 MiB
random_01 AC 938 ms 157.34 MiB
random_02 AC 437 ms 65.83 MiB
random_03 AC 196 ms 74.84 MiB
random_04 AC 284 ms 80.31 MiB
random_05 AC 629 ms 130.58 MiB
random_06 AC 552 ms 127.59 MiB
random_07 AC 109 ms 42.64 MiB
random_08 AC 454 ms 110.64 MiB
random_09 AC 285 ms 68.21 MiB
random_dag_00 AC 970 ms 138.33 MiB
random_dag_01 AC 1013 ms 150.09 MiB
random_dag_02 AC 503 ms 69.58 MiB
random_dag_03 AC 202 ms 74.71 MiB
random_dag_04 AC 295 ms 79.30 MiB
random_dag_05 AC 794 ms 124.09 MiB
random_dag_06 AC 585 ms 123.83 MiB
random_dag_07 AC 106 ms 42.58 MiB
random_dag_08 AC 614 ms 107.31 MiB
random_dag_09 AC 355 ms 67.34 MiB
random_dag_dense_00 AC 297 ms 79.96 MiB
random_dag_dense_01 AC 265 ms 59.84 MiB
random_dag_dense_02 AC 1868 ms 61.45 MiB
random_dag_dense_03 AC 640 ms 60.84 MiB
random_dag_dense_04 AC 384 ms 80.09 MiB
random_dense_00 AC 267 ms 89.34 MiB
random_dense_01 AC 216 ms 63.09 MiB
random_dense_02 AC 179 ms 59.96 MiB
random_dense_03 AC 209 ms 62.08 MiB
random_dense_04 AC 324 ms 90.09 MiB

import sys input = sys.stdin.readline from array import array from collections import deque def cycle(G): n = len(G) seen = [0] * n finished = [0] * n for root in range(n): if seen[root]: continue hist = deque() que = deque() que.append(~root); que.append(root) while que: v = que.pop() if v >= 0: seen[v] = 1 hist.append(v) for e in G[v]: if finished[e]: continue if seen[e] and not finished[e]: while hist: if hist[0] == e: break hist.popleft() return list(hist) que.append(~e); que.append(e) else: hist.pop() finished[~v] = 1 return [] n, m = map(int, input().split()) es = [[] for _ in range(n)] d = [{} for _ in range(n)] for i in range(m): start, end = map(int, input().split()) # start -= 1; end -= 1 es[start].append(end) d[start][end] = i c = cycle(es) if not c: print(-1) else: c.append(c[0]) res = [] for i, j in zip(c, c[1:]): res.append(d[i][j]) print(len(res)) print(*res, sep="\n")