結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー norioc
提出日時 2025-11-20 02:43:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 710 ms / 2,000 ms
コード長 1,401 bytes
コンパイル時間 500 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 156,908 KB
最終ジャッジ日時 2025-11-20 02:43:58
合計ジャッジ時間 18,140 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque, defaultdict

WIN = 0
LOSE = 1
DRAW = 2


def detect_graph_game(n: int, adj: dict[int, list[int]]) -> list[int]:
    """
    頂点 0 にコマを置き、コマを動かせなくなった方が負け
    n: 頂点数
    adj: {頂点: [隣接頂点, ...]}
    return: 結果(WIN, LOSE, DRAW)
    """
    res = [DRAW] * n
    r_adj = defaultdict(list)  # 逆辺
    outdegs = [0] * n
    q = deque()
    for i in range(n):
        nexts = adj[i]
        for to in nexts:
            r_adj[to].append(i)

        outdegs[i] = len(nexts)
        if len(nexts) == 0:
            res[i] = LOSE  # 遷移できないなら負け
            q.append(i)

    while q:
        v = q.popleft()

        for prev in r_adj[v]:  # 遷移元
            if res[prev] != DRAW: continue

            if res[v] == LOSE:  # 負けで遷移できるなら勝ち
                res[prev] = WIN
                q.append(prev)
            else:
                outdegs[prev] -= 1
                if outdegs[prev] == 0:
                    res[prev] = LOSE
                    q.append(prev)

    return res


N, M = map(int, input().split())
adj = defaultdict(list)
for _ in range(M):
    U, V = map(lambda x: int(x)-1, input().split())
    adj[U].append(V)

res = detect_graph_game(N, adj)
if res[0] == WIN:
    print('Alice')
elif res[0] == LOSE:
    print('Bob')
else:
    print('Draw')
0