結果

問題 No.1865 Make Cycle
ユーザー brthyyjp
提出日時 2022-03-07 20:59:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 711 ms / 3,000 ms
コード長 1,373 bytes
コンパイル時間 581 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 208,924 KB
最終ジャッジ日時 2024-07-22 17:25:33
合計ジャッジ時間 10,630 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
def cycle_detectable_topological_sort(g, ind):
    V = len(g)
    order = []
    depth = [-1]*V
    for i in range(V):
        if not ind[i]:
            order.append(i)
            depth[i] = 0

    q = deque(order)
    while q:
        v = q.popleft()
        cur_depth = depth[v]
        for u in g[v]:
            ind[u] -= 1
            if not ind[u]:
                depth[u] = max(depth[u], cur_depth+1)
                q.append(u)
                order.append(u)
    if len(order) == V:
        return (order, depth)
    else:
        return (None, None)

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, q = map(int, input().split())
AB = []
for i in range(q):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    AB.append((a, b))

g = [[] for i in range(n)]
ind = [0]*n
for a, b in AB:
    g[a].append(b)
    ind[b] += 1

order, _ = cycle_detectable_topological_sort(g, ind)
if order is not None:
    print(-1)
    exit()

def is_ok(x):
    g = [[] for i in range(n)]
    ind = [0]*n
    for i in range(x+1):
        a, b = AB[i]
        g[a].append(b)
        ind[b] += 1
    order, _ = cycle_detectable_topological_sort(g, ind)
    return order is None

ng = -1
ok = q-1
while ng+1<ok:
    mid = (ng+ok)//2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok+1)
0