// Gemini 2.5 Pro に嘘ヒントを教えて出力された嘘解法 #include #include #include #include // 縮約グラフの重複辺除去 #include // ACLのSCCライブラリ using namespace std; using namespace atcoder; // 勝敗の状態 (0: LOSE, 1: WIN, 2: DRAW) enum GameResult { LOSE = 0, WIN = 1, DRAW = 2 }; int main() { int N, M; cin >> N >> M; scc_graph graph(N); vector> edges; // 元の辺リスト (0-indexed) vector has_self_loop(N, false); // 自己ループ判定用 for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; u--; // 0-indexed に v--; graph.add_edge(u, v); edges.push_back({u, v}); if (u == v) { has_self_loop[u] = true; } } // --- 1. SCC --- vector> sccs = graph.scc(); int num_scc = sccs.size(); // scc_id[v] = 頂点vが属するSCCのID vector scc_id(N); for (int i = 0; i < num_scc; ++i) { for (int v : sccs[i]) { scc_id[v] = i; } } // --- 2. サイクル判定 (DRAWの可能性) --- // scc_is_draw[i] = SCC i がサイクル(DRAW)可能か vector scc_is_draw(num_scc, false); for (int i = 0; i < num_scc; ++i) { if (sccs[i].size() >= 2) { // 頂点数が2以上ならサイクル scc_is_draw[i] = true; } else { // 頂点数が1の場合、自己ループがあるか int u = sccs[i][0]; if (has_self_loop[u]) { scc_is_draw[i] = true; } } } // --- 3. 縮約グラフ構築 --- // scc_adj[i] = SCC i から到達可能なSCCのIDリスト (重複なし) vector> scc_adj(num_scc); for (const auto& edge : edges) { int u_id = scc_id[edge.first]; int v_id = scc_id[edge.second]; if (u_id != v_id) { scc_adj[u_id].insert(v_id); } } // --- 4. 後退解析 (DP) --- // dp[i] = SCC i からゲームを始めたときの勝敗 vector dp(num_scc); // ACLのSCCはトポロジカルソート順なので、IDの大きい方(末端)から処理 for (int i = num_scc - 1; i >= 0; --i) { // デフォルトは LOSE (遷移先がすべて WIN か、遷移先なし) dp[i] = LOSE; bool can_move_to_draw = false; // 遷移先をチェック for (int next_scc_id : scc_adj[i]) { if (dp[next_scc_id] == LOSE) { // 優先度1: 相手をLOSEにできるなら、自分はWIN dp[i] = WIN; break; // このSCCの判定終了 } if (dp[next_scc_id] == DRAW) { can_move_to_draw = true; } } // (もし dp[i] == WIN なら、この continue が実行される) if (dp[i] == WIN) continue; // (LOSEには行けなかった場合) if (scc_is_draw[i]) { // 優先度2: 自分がサイクル持ち (DRAW可能) dp[i] = DRAW; } else if (can_move_to_draw) { // 優先度3: 自分がサイクル持ちでないが、DRAW には行ける dp[i] = DRAW; } // 優先度4: (dp[i] == LOSE のまま) // LOSEに行けず、自分もサイクルでなく、DRAWにも行けない // = 遷移先はすべてWIN、または遷移先なし } // --- 5. 判定 --- int start_scc_id = scc_id[0]; // スタート(頂点1 -> 0) if (dp[start_scc_id] == WIN) { cout << "Alice" << endl; } else if (dp[start_scc_id] == LOSE) { cout << "Bob" << endl; } else { // DRAW cout << "Draw" << endl; } return 0; }