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

• 問題: No.3508 OR Mapping
• ユーザー: gojoxd
• 提出日時: 2026-04-18 19:34:52
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 340 ms / 2,000 ms
• コード長: 4,637 bytes
• コンパイル時間: 1,862 ms
• コンパイル使用メモリ: 189,964 KB
• 実行使用メモリ: 124,984 KB
• 最終ジャッジ日時: 2026-04-18 19:35:12
• 合計ジャッジ時間: 18,129 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

using namespace std;

const int MAXN = 500005;
vector<int> adj[MAXN], rev_adj[MAXN];
vector<int> order;
bool visited[MAXN];
int scc_id[MAXN];
vector<vector<int>> scc_nodes;

// Kosaraju's DFS 1
void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs1(v);
    }
    order.push_back(u);
}

// Kosaraju's DFS 2
void dfs2(int u, int id) {
    visited[u] = true;
    scc_id[u] = id;
    scc_nodes.back().push_back(u);
    for (int v : rev_adj[u]) {
        if (!visited[v]) dfs2(v, id);
    }
}

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

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

    // Phase 1: Build Strongly Connected Components (Kosaraju's Algorithm)
    for (int i = 1; i <= n; i++) visited[i] = false;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) dfs1(i);
    }

    for (int i = 1; i <= n; i++) visited[i] = false;

    int current_scc = 0;
    // Process in reverse post-order to topologically sort the SCCs
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        if (!visited[u]) {
            scc_nodes.push_back(vector<int>());
            dfs2(u, current_scc);
            current_scc++;
        }
    }

    // Rule 0: Vertex 1 must be in the absolute first SCC (Topological Source)
    if (scc_id[1] != 0) {
        cout << "No\n";
        return 0;
    }

    // Rule 1: The SCCs must form a simple path (Hamiltonian path) to ensure all can be visited.
    for (int i = 0; i < current_scc - 1; i++) {
        bool has_edge = false;
        for (int u : scc_nodes[i]) {
            for (int v : adj[u]) {
                if (scc_id[v] == i + 1) {
                    has_edge = true;
                    break;
                }
            }
            if (has_edge) break;
        }
        if (!has_edge) {
            cout << "No\n";
            return 0;
        }
    }

    // Phase 2: Bipartite Testing & Validation
    vector<int> type(current_scc);
    // 0 = NON_BIPARTITE, 1 = SINGLE, 2 = BIPARTITE_MULTI
    vector<int> color(n + 1, -1);

    for (int i = 0; i < current_scc; i++) {
        bool is_bip = true;
        for (int u : scc_nodes[i]) {
            if (color[u] == -1) {
                color[u] = 0;
                queue<int> q;
                q.push(u);
                while (!q.empty()) {
                    int curr = q.front();
                    q.pop();
                    // Forward Edges
                    for (int nxt : adj[curr]) {
                        if (scc_id[nxt] != i) continue;
                        if (color[nxt] == -1) {
                            color[nxt] = color[curr] ^ 1;
                            q.push(nxt);
                        } else if (color[nxt] == color[curr]) {
                            is_bip = false;
                        }
                    }
                    // Reverse Edges (Treat internal graph as Undirected for bipartite check)
                    for (int nxt : rev_adj[curr]) {
                        if (scc_id[nxt] != i) continue;
                        if (color[nxt] == -1) {
                            color[nxt] = color[curr] ^ 1;
                            q.push(nxt);
                        } else if (color[nxt] == color[curr]) {
                            is_bip = false;
                        }
                    }
                }
            }
        }
        
        if (!is_bip) {
            type[i] = 0; // Contains an odd cycle
        } else {
            if (scc_nodes[i].size() == 1) type[i] = 1; // Standalone single-vertex
            else type[i] = 2; // Bipartite block with 2+ nodes
        }
    }

    // Rule 2: The very first SCC containing vertex 1 must be non-bipartite
    if (type[0] == 1) {
        cout << "No\n";
        return 0;
    }

    for (int i = 0; i < current_scc; i++) {
        // Rule 3: We cannot have any multi-node bipartite SCCs anywhere 
        if (type[i] == 2) {
            cout << "No\n";
            return 0;
        }
    }

    for (int i = 0; i < current_scc - 1; i++) {
        // Rule 4: We cannot have two sequential single vertices with no way to delay the clock
        if (type[i] == 1 && type[i + 1] == 1) {
            cout << "No\n";
            return 0;
        }
    }

    // Graph beautifully passes all logical properties 
    cout << "Yes\n";
    return 0;
}