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

• 問題: No.3508 OR Mapping
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 06:31:39
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 513 ms / 2,000 ms
• コード長: 3,804 bytes
• コンパイル時間: 1,892 ms
• コンパイル使用メモリ: 208,016 KB
• 実行使用メモリ: 153,904 KB
• 最終ジャッジ日時: 2026-04-18 06:32:07
• 合計ジャッジ時間: 22,502 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
long long k;
vector<vector<int>> adj;
vector<vector<int>> rev_adj;
vector<int> order;
vector<bool> vis;
vector<int> scc_id;
vector<vector<int>> scc_nodes;
void dfs1(int u) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) dfs1(v);
    }
    order.push_back(u);
}
void dfs2(int u, int id) {
    scc_id[u] = id;
    scc_nodes.back().push_back(u);
    for (int v : rev_adj[u]) {
        if (scc_id[v] == -1) dfs2(v, id);
    }
}
enum Type { SINGLE, ODD, INVALID };
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> n >> m >> k)) return 0;
    adj.resize(n + 1);
    rev_adj.resize(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);
    }
    vis.assign(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) dfs1(i);
    }
    scc_id.assign(n + 1, -1);
    int num_sccs = 0;
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        if (scc_id[u] == -1) {
            scc_nodes.push_back(vector<int>());
            dfs2(u, num_sccs++);
        }
    }
    vector<vector<int>> scc_adj(num_sccs);
    vector<int> in_degree(num_sccs, 0);
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                scc_adj[scc_id[u]].push_back(scc_id[v]);
            }
        }
    }
    for (int i = 0; i < num_sccs; ++i) {
        sort(scc_adj[i].begin(), scc_adj[i].end());
        scc_adj[i].erase(unique(scc_adj[i].begin(), scc_adj[i].end()), scc_adj[i].end());
        for (int v : scc_adj[i]) {
            in_degree[v]++;
        }
    }
    queue<int> q;
    for (int i = 0; i < num_sccs; ++i) {
        if (in_degree[i] == 0) q.push(i);
    }
    vector<int> path;
    while (!q.empty()) {
        if (q.size() > 1) {
            cout << "No\n";
            return 0;
        }
        int u = q.front();
        q.pop();
        path.push_back(u);
        for (int v : scc_adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) q.push(v);
        }
    }
    if (path.size() != num_sccs) {
        cout << "No\n";
        return 0;
    }
    if (scc_id[1] != path[0]) {
        cout << "No\n";
        return 0;
    }
    vector<Type> scc_type(num_sccs);
    for (int i = 0; i < num_sccs; ++i) {
        if (scc_nodes[i].size() == 1) {
            scc_type[i] = SINGLE;
        } else {
            bool is_bip = true;
            vector<int> color(n + 1, -1);
            int start = scc_nodes[i][0];
            color[start] = 0;
            queue<int> bq;
            bq.push(start);
            while (!bq.empty()) {
                int u = bq.front();
                bq.pop();
                for (int v : adj[u]) {
                    if (scc_id[v] == i) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u];
                            bq.push(v);
                        } else if (color[v] == color[u]) {
                            is_bip = false;
                        }
                    }
                }
            }
            if (is_bip) scc_type[i] = INVALID;
            else scc_type[i] = ODD;
        }
    }
    if (scc_type[path[0]] != ODD) {
        cout << "No\n";
        return 0;
    }
    for (int i = 0; i < num_sccs; ++i) {
        if (scc_type[path[i]] == INVALID) {
            cout << "No\n";
            return 0;
        }
    }
    for (int i = 0; i < num_sccs - 1; ++i) {
        if (scc_type[path[i]] == SINGLE && scc_type[path[i+1]] == SINGLE) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}