結果
問題 | No.1865 Make Cycle |
ユーザー |
|
提出日時 | 2022-06-28 02:40:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 883 ms / 3,000 ms |
コード長 | 1,103 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,624 KB |
実行使用メモリ | 272,824 KB |
最終ジャッジ日時 | 2024-11-20 12:16:12 |
合計ジャッジ時間 | 13,924 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
import sysfrom collections import dequeinput = lambda: sys.stdin.readline().rstrip()def topological_sort(G: list) -> list:"Return topological_sort. / O(|V|+|E|)"# 0-indexed# len(toposo) != n: 閉路が存在n = len(G)in_cnt = [0] * nouts = [[] for _ in range(n)]for v in range(n):for x in G[v]:in_cnt[x] += 1outs[v].append(x)res = []todo = deque([i for i in range(n) if in_cnt[i] == 0])while todo:v = todo.popleft()res.append(v)for x in outs[v]:in_cnt[x] -= 1if in_cnt[x] == 0:todo.append(x)return res# ----------------------- #n, q = map(int, input().split())AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(q)]def isok(mid):G = [[] for _ in range(n)]for i in range(mid):a = AB[i][0]b = AB[i][1]G[a].append(b)toposo = topological_sort(G)if len(toposo) != n:return Trueelse:return Falseok, ng = q+1, -1while ok - ng > 1:mid = (ok + ng) // 2if isok(mid):ok = midelse:ng = midif ok == q+1:print(-1)else:print(ok)