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

• 問題: No.3508 OR Mapping
• ユーザー: e032_Ashmit_Rana
• 提出日時: 2026-04-18 01:19:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 446 ms / 2,000 ms
• コード長: 3,889 bytes
• コンパイル時間: 2,745 ms
• コンパイル使用メモリ: 360,648 KB
• 実行使用メモリ: 96,140 KB
• 最終ジャッジ日時: 2026-04-18 01:19:27
• 合計ジャッジ時間: 16,054 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<vector<int>> g(N), rg(N);
    vector<pair<int, int>> edges;
    edges.reserve(M);

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        rg[v].push_back(u);
        edges.push_back({u, v});
    }

    vector<char> used(N, 0);
    vector<int> order;
    order.reserve(N);

    for (int s = 0; s < N; ++s) {
        if (used[s]) continue;

        vector<pair<int, int>> st;
        st.push_back({s, 0});
        used[s] = 1;

        while (!st.empty()) {
            int u = st.back().first;
            int &it = st.back().second;

            if (it < (int)g[u].size()) {
                int v = g[u][it++];
                if (!used[v]) {
                    used[v] = 1;
                    st.push_back({v, 0});
                }
            } else {
                order.push_back(u);
                st.pop_back();
            }
        }
    }

    vector<int> comp(N, -1);
    vector<vector<int>> members;

    for (int i = N - 1; i >= 0; --i) {
        int s = order[i];
        if (comp[s] != -1) continue;

        int cid = (int)members.size();
        members.push_back({});

        vector<int> st = {s};
        comp[s] = cid;
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            members[cid].push_back(u);

            for (int v : rg[u]) {
                if (comp[v] == -1) {
                    comp[v] = cid;
                    st.push_back(v);
                }
            }
        }
    }

    int C = (int)members.size();
    vector<char> singleton(C, 0);
    for (int c = 0; c < C; ++c) {
        singleton[c] = (members[c].size() == 1);
    }

    auto no = []() {
        cout << "No\n";
        return 0;
    };

    vector<int> parity(N, -1);
    for (int c = 0; c < C; ++c) {
        if (singleton[c]) continue;

        bool has_odd_cycle = false;
        int root = members[c][0];
        parity[root] = 0;
        vector<int> st = {root};

        while (!st.empty()) {
            int u = st.back();
            st.pop_back();

            for (int v : g[u]) {
                if (comp[v] != c) continue;

                int want = parity[u] ^ 1;
                if (parity[v] == -1) {
                    parity[v] = want;
                    st.push_back(v);
                } else if (parity[v] != want) {
                    has_odd_cycle = true;
                }
            }
        }

        if (!has_odd_cycle) return no();
    }

    int start_comp = comp[0];
    if (singleton[start_comp]) return no();

    vector<pair<int, int>> dag_edges;
    dag_edges.reserve(M);
    for (auto [u, v] : edges) {
        int a = comp[u], b = comp[v];
        if (a != b) dag_edges.push_back({a, b});
    }
    sort(dag_edges.begin(), dag_edges.end());
    dag_edges.erase(unique(dag_edges.begin(), dag_edges.end()), dag_edges.end());

    vector<vector<int>> dag(C);
    vector<int> indeg(C, 0);
    for (auto [a, b] : dag_edges) {
        dag[a].push_back(b);
        ++indeg[b];
    }

    deque<int> q;
    for (int c = 0; c < C; ++c) {
        if (indeg[c] == 0) q.push_back(c);
    }

    vector<int> topo;
    topo.reserve(C);
    while (!q.empty()) {
        if (q.size() != 1) return no();

        int u = q.front();
        q.pop_front();
        topo.push_back(u);

        for (int v : dag[u]) {
            --indeg[v];
            if (indeg[v] == 0) q.push_back(v);
        }
    }

    if ((int)topo.size() != C) return no();
    if (topo[0] != start_comp) return no();

    for (int i = 0; i + 1 < C; ++i) {
        if (singleton[topo[i]] && singleton[topo[i + 1]]) return no();
    }

    cout << "Yes\n";
    return 0;
}