結果

問題 No.1865 Make Cycle
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:29:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,338 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 100,552 KB
最終ジャッジ日時 2025-04-15 21:32:34
合計ジャッジ時間 3,021 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1

    parent = list(range(N + 1))  # 1-based indexing

    def find(u):
        # Check if B is an ancestor of u
        original_u = u
        while True:
            if parent[u] == u:
                break
            u = parent[u]
        # Path compression
        temp = original_u
        while parent[temp] != u:
            next_temp = parent[temp]
            parent[temp] = u
            temp = next_temp
        return u

    for i in range(1, Q + 1):
        A = int(data[idx])
        idx += 1
        B = int(data[idx])
        idx += 1

        # Check if B is an ancestor of A
        current = A
        found = False
        visited = set()
        while True:
            if current == B:
                found = True
                break
            if current in visited:
                break
            visited.add(current)
            p = parent[current]
            if p == current:
                break
            current = p
        if found:
            print(i)
            return
        # Otherwise, set B's parent to A
        parent[B] = A

    print(-1)

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