#1159438 (C++23) No.3508 OR Mapping

• 問題: No.3508 OR Mapping
• ユーザー: 왕지후
• 提出日時: 2026-04-18 11:28:57
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 327 ms / 2,000 ms
• コード長: 3,728 bytes
• コンパイル時間: 1,796 ms
• コンパイル使用メモリ: 199,688 KB
• 実行使用メモリ: 128,432 KB
• 最終ジャッジ日時: 2026-04-18 11:29:15
• 合計ジャッジ時間: 17,551 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 65

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    long long k; // 判定には使わないが読み込む
    if (!(cin >> n >> m >> k)) return 0;

    vector<vector<int>> adj(n + 1);
    vector<vector<int>> rev_adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        rev_adj[v].push_back(u);
    }

    // --- 1. KosarajuのアルゴリズムでSCC分解 ---
    vector<bool> vis(n + 1, false);
    vector<int> order;

    auto dfs1 = [&](auto& self, int u) -> void {
        vis[u] = true;
        for (int v : adj[u]) {
            if (!vis[v]) self(self, v);
        }
        order.push_back(u);
    };

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs1(dfs1, i);
    }

    reverse(order.begin(), order.end());
    vis.assign(n + 1, false);
    vector<int> comp(n + 1, -1);
    vector<vector<int>> sccs;

    auto dfs2 = [&](auto& self, int u, int c) -> void {
        vis[u] = true;
        comp[u] = c;
        sccs.back().push_back(u);
        for (int v : rev_adj[u]) {
            if (!vis[v]) self(self, v, c);
        }
    };

    for (int u : order) {
        if (!vis[u]) {
            sccs.push_back({});
            dfs2(dfs2, u, sccs.size() - 1);
        }
    }

    int num_scc = sccs.size();

    // --- 2. スタート地点の確認 ---
    bool has_1 = false;
    for (int u : sccs[0]) {
        if (u == 1) has_1 = true;
    }
    if (!has_1) {
        cout << "No\n";
        return 0;
    }

    // --- 3. 全SCCを一筆書きできるか（ハミルトンパスの確認） ---
    for (int i = 0; i < num_scc - 1; i++) {
        bool edge_exists = false;
        for (int u : sccs[i]) {
            for (int v : adj[u]) {
                if (comp[v] == i + 1) {
                    edge_exists = true;
                    break;
                }
            }
            if (edge_exists) break;
        }
        if (!edge_exists) {
            cout << "No\n";
            return 0;
        }
    }

    // --- 4. 各SCCの条件チェック ---
    for (int i = 0; i < num_scc; i++) {
        if (sccs[i].size() == 1) {
            // 単一頂点のSCC
            if (i == 0) {
                cout << "No\n"; // 先頭が単一頂点はNG
                return 0;
            }
            if (i > 0 && sccs[i - 1].size() == 1) {
                cout << "No\n"; // 単一頂点の連続はNG
                return 0;
            }
        } else {
            // 複数頂点のSCC (二部グラフ判定)
            bool is_bipartite = true;
            vector<int> color(n + 1, -1);
            int start = sccs[i][0];
            color[start] = 0;
            queue<int> q;
            q.push(start);

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (int v : adj[u]) {
                    // 同じSCC内の辺のみ考慮
                    if (comp[v] == comp[u]) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u];
                            q.push(v);
                        } else if (color[v] == color[u]) {
                            is_bipartite = false; // 奇数長閉路を発見！
                        }
                    }
                }
            }

            if (is_bipartite) {
                cout << "No\n"; // 二部グラフのままならNG
                return 0;
            }
        }
    }

    // すべての試練を乗り越えればYes!
    cout << "Yes\n";
    return 0;
}