結果

問題 No.1865 Make Cycle
ユーザー LyricalMaestro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

## 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()
0