結果

問題 No.1865 Make Cycle
コンテスト
ユーザー LyricalMaestro
提出日時 2024-08-03 01:36:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,413 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 99,892 KB
最終ジャッジ日時 2024-08-03 01:36:14
合計ジャッジ時間 7,741 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1865

from collections import deque

def solve(N, next_nodes, border_q):
    queue = deque()
    passed = [-1] * N
    p_id = 0    
    for s_i in range(N):
        if passed[s_i] == -1:
            queue.append(s_i)
            passed[s_i] = p_id
            while len(queue) > 0:
                v = queue.popleft()
                for w, q in next_nodes[v].items():
                    if q > border_q:
                        continue

                    if w == s_i:
                        return True

                    if passed[w] == -1:
                        passed[w] = p_id
                        queue.append(w)

            p_id += 1
    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())
        a -= 1
        b -= 1
        if b not in next_nodes[a]:
            next_nodes[a][b] = i

    # 全て繋げた状態で    
    ans = solve(N, next_nodes, Q - 1)
    if not ans:
        print(-1)
        return
    
    low = 0
    high = Q - 1
    while high - low > 1:
        mid = (high + low) // 2
        if solve(N, next_nodes, mid):
            high = mid
        else:
            low = mid
    if solve(N, next_nodes, low):
        print(low + 1)
    else:
        print(high + 1)

        



if __name__ == "__main__":
    main()
0