結果

問題 No.2403 "Eight" Bridges of Königsberg
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:22:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,387 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 90,684 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:24:58
合計ジャッジ時間 3,384 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // For std::iota
#include <set>
#include <algorithm> // For std::max

// DSU structure
struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i for 0 to n
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]); // Path compression
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j; 
        }
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    if (m == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    std::vector<long long> in_degree(n + 1, 0);
    std::vector<long long> out_degree(n + 1, 0);
    std::vector<std::pair<int, int>> edges(m);
    std::set<int> active_nodes; // To keep track of nodes involved in edges

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        edges[i] = {u, v};
        out_degree[u]++;
        in_degree[v]++;
        active_nodes.insert(u);
        active_nodes.insert(v);
    }

    // Calculate P_val = sum of (out_degree - in_degree) for nodes where out_degree > in_degree
    long long p_val = 0;
    for (int i = 1; i <= n; ++i) {
        if (out_degree[i] > in_degree[i]) {
            p_val += (out_degree[i] - in_degree[i]);
        }
    }

    // Calculate K_deg: edges needed for degree balancing for an Eulerian path
    long long k_deg = std::max(0LL, p_val - 1);

    // Calculate K_conn: edges needed for weak connectivity
    DSU dsu(n);
    for (const auto& edge : edges) {
        dsu.unite(edge.first, edge.second);
    }

    int num_components = 0;
    // active_nodes must be non-empty if m > 0
    if (!active_nodes.empty()) { 
        std::set<int> roots;
        for (int node_val : active_nodes) {
            roots.insert(dsu.find(node_val));
        }
        num_components = roots.size();
    }
    // Since m > 0, active_nodes is not empty, so num_components >= 1.
    long long k_conn = num_components - 1;

    // The minimum number of edges to add is max(K_deg, K_conn)
    std::cout << std::max(k_deg, k_conn) << std::endl;

    return 0;
}
0