結果
問題 |
No.1865 Make Cycle
|
ユーザー |
|
提出日時 | 2024-11-02 13:07:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 785 ms / 3,000 ms |
コード長 | 1,788 bytes |
コンパイル時間 | 501 ms |
コンパイル使用メモリ | 82,716 KB |
実行使用メモリ | 111,932 KB |
最終ジャッジ日時 | 2024-11-02 13:07:19 |
合計ジャッジ時間 | 12,955 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
## https://yukicoder.me/problems/no/1865 from collections import deque MAX_INT = 10 ** 18 def exists_cycle(N, next_nodes, border): passed = [False] * N passed2 = [False] * N for s in range(N): if not passed[s]: passed[s] = True stack = deque() stack.append((s, 0)) while len(stack) > 0: v, index = stack.pop() passed2[v] = True while index < len(next_nodes[v]): w, i = next_nodes[v][index] if i > border: index += 1 continue if passed[w]: if passed2[w]: return True else: index += 1 continue stack.append((v, index + 1)) stack.append((w, 0)) passed[w] = True break if index == len(next_nodes[v]): passed2[v] = False return False def main(): N, Q = map(int, input().split()) next_nodes = [[] for _ in range(N)] for i in range(Q): A, B = map(int ,input().split()) next_nodes[A - 1].append((B - 1, i)) # そもそも閉路が存在するか? if not exists_cycle(N, next_nodes, Q - 1): print(-1) return low = 0 high = Q - 1 while high - low > 1: mid = (high + low ) //2 if exists_cycle(N, next_nodes, mid): high = mid else: low = mid if exists_cycle(N, next_nodes, low): print(low + 1) else: print(high + 1) if __name__ == "__main__": main()