結果

問題 No.1865 Make Cycle
コンテスト
ユーザー norioc
提出日時 2026-08-23 16:29:41
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 992 ms / 3,000 ms
+ 176µs
コード長 2,682 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 544 ms
コンパイル使用メモリ 96,236 KB
実行使用メモリ 290,676 KB
最終ジャッジ日時 2026-08-23 16:30:00
合計ジャッジ時間 18,220 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict
from enum import Enum, auto
import sys
sys.setrecursionlimit(10**6)


class E(Enum):
    NOT_FOUND = auto()  # 閉路は見つからなかった
    BUILDING = auto()   # 閉路を構築中
    COMPLETED = auto()  # 閉路を構築済み


def detect_directed_cycle(n: int, adj):
    """
    有向グラフの閉路を求める

    n: 頂点数
    adj: 隣接頂点 {v: [隣接頂点, ...]}
    return:
        (閉路が存在するか, 閉路の頂点パス)
    """

    def dfs(v, dists, used):  # -> tuple[E, int, tuple[int, int | None] | None]:
        """
        return:
            (state, cycle_start, path)
            state: E
            cycle_start: 閉路の始点
            path: 閉路の頂点パス
        """
        for to in adj[v]:
            if used[to]: continue

            nd = dists[v] + 1
            if dists[to] < nd:  # 閉路が見つかった
                return E.BUILDING, to, (v, None)
            elif dists[to] == INF:
                dists[to] = nd
                state, cycle_start, path = dfs(to, dists, used)
                used[to] = True  # 帰りがけ

                if state == E.COMPLETED:
                    return state, cycle_start, path
                elif state == E.BUILDING:
                    if v == cycle_start:
                        return E.COMPLETED, cycle_start, (v, path)
                    else:
                        return state, cycle_start, (v, path)

        return E.NOT_FOUND, -1, None

    dists = [INF] * n
    used = [False] * n
    for i in range(n):
        if used[i]: continue

        dists[i] = 0
        state, _, path = dfs(i, dists, used)
        used[i] = True  # 帰りがけ
        if state == E.COMPLETED:
            p = path
            cycle_path = []
            while p is not None:
                a, p = p
                cycle_path.append(a)

            return True, cycle_path

    return False, None


def bsearch_right(low: int, high: int, pred) -> int:
    assert pred(high)
    lo = low
    hi = high
    res = high
    while lo <= hi:
        m = (lo + hi) // 2
        if pred(m):
            res = min(res, m)
            hi = m - 1
        else:
            lo = m + 1

    return res


def can(m: int) -> bool:
    adj = defaultdict(list)
    for i in range(m):
        u, v = edges[i]
        adj[u].append(v)

    found, _ = detect_directed_cycle(N, adj)
    return found


INF = 1 << 62
N, Q = map(int, input().split())

edges = []
for _ in range(Q):
    A, B = map(lambda x: int(x)-1, input().split())
    edges.append((A, B))

if not can(Q):
    print(-1)
    exit()

res = bsearch_right(1, Q, can)
print(res)
0