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

• 問題: No.3508 OR Mapping
• ユーザー: Naru820
• 提出日時: 2026-03-28 11:14:09
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 353 ms / 2,000 ms
• コード長: 4,220 bytes
• コンパイル時間: 2,198 ms
• コンパイル使用メモリ: 199,924 KB
• 実行使用メモリ: 134,328 KB
• 最終ジャッジ日時: 2026-04-17 19:49:44
• 合計ジャッジ時間: 16,213 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

// gemini test
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;
long long k;
vector<vector<int>> adj;

int timer = 0, scc_cnt = 0;
vector<int> dfn, low, scc;
vector<int> st;
vector<bool> in_st;
vector<vector<int>> scc_nodes;

void dfs(int u) {
    dfn[u] = low[u] = ++timer;
    st.push_back(u);
    in_st[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (in_st[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc_cnt++;
        scc_nodes.push_back(vector<int>());
        while (true) {
            int v = st.back();
            st.pop_back();
            in_st[v] = false;
            scc[v] = scc_cnt;
            scc_nodes.back().push_back(v);
            if (u == v) break;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> n >> m >> k)) return 0;

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

    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc.assign(n + 1, 0);
    in_st.assign(n + 1, false);
    scc_nodes.push_back(vector<int>()); // index 0 をダミーで埋める

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            dfs(i);
        }
    }

    int C = scc_cnt;
    vector<int> top_order(C + 1);
    for (int i = 1; i <= C; i++) {
        // Tarjanのアルゴリズムはトポロジカルソートの逆順でSCCを出力する
        top_order[i] = C - i + 1;
    }

    // 1. 頂点1が最初のSCCに含まれているか
    if (scc[1] != top_order[1]) {
        cout << "No\n";
        return 0;
    }

    // 2. 全てのSCCが一直線のパス（ハミルトンパス）を形成しているか
    for (int i = 1; i < C; i++) {
        int u_scc = top_order[i];
        int v_scc = top_order[i + 1];
        bool has_edge = false;
        for (int u : scc_nodes[u_scc]) {
            for (int v : adj[u]) {
                if (scc[v] == v_scc) {
                    has_edge = true;
                    break;
                }
            }
            if (has_edge) break;
        }
        if (!has_edge) {
            cout << "No\n";
            return 0;
        }
    }

    vector<int> type(C + 1);
    vector<int> color(n + 1, -1);
    for (int i = 1; i <= C; i++) {
        int u_scc = i;
        if (scc_nodes[u_scc].size() == 1) {
            type[u_scc] = 1; // 単一頂点SCC
        } else {
            // SCCが二部グラフか(奇数長のサイクルを持たないか)判定
            bool is_bip = true;
            for (int v : scc_nodes[u_scc]) color[v] = -1;
            int start_node = scc_nodes[u_scc][0];
            queue<int> q;
            q.push(start_node);
            color[start_node] = 0;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : adj[u]) {
                    if (scc[v] == u_scc) {
                        if (color[v] == -1) {
                            color[v] = color[u] ^ 1;
                            q.push(v);
                        } else if (color[v] != (color[u] ^ 1)) {
                            is_bip = false; // 奇数サイクル発見
                        }
                    }
                }
            }
            // 3. 2頂点以上の二部グラフは条件を満たせないため不可
            if (is_bip) {
                cout << "No\n";
                return 0;
            }
            type[u_scc] = 2; // 奇数サイクルを持つSCC
        }
    }

    // 4. 最初が単一頂点のSCCは不可（開始時に未更新で抜けてしまうため）
    if (type[top_order[1]] == 1) {
        cout << "No\n";
        return 0;
    }

    // 5. 単一頂点のSCCは連続してはいけない
    for (int i = 1; i < C; i++) {
        if (type[top_order[i]] == 1 && type[top_order[i + 1]] == 1) {
            cout << "No\n";
            return 0;
        }
    }

    // 全ての条件をクリア
    cout << "Yes\n";
    return 0;
}