Ant Trip

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1601 字
多组数据，每组给N个点M条互不相同的无向边且
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1530
// 题意：多组数据（读到 EOF），每组给 N 个点 M 条互不相同的无向边且无自环，问至少几笔才能把所有边都画一遍（一笔画中途笔不离开纸），每组输出一个答案。
// 思路：按连通块分开算：某个连通块若所有点度数都是偶数，它本身就有欧拉回路，一笔画完；否则需要「奇度点个数除以 2」笔，把所有块的笔数加起来。
// 1. 一个连通块里奇度点个数必为偶数，每笔从一个奇度点走到另一个奇度点，正好消耗两个奇度点。
// 2. 没有任何边的孤立点不构成连通块贡献，统计时要按「块内是否有边」来筛掉它们。
// 复杂度：O(N + M) 时间 / O(N + M) 空间
// 易错点：输入没有组数也没有结束标志，必须读到 EOF 为止，多读一个数就会把下一组的 N 吃掉。
// 易错点：全偶度数的连通块答案是 1 而不是 0，哪怕它只有一个点（此时它其实没有边，应跳过不算）。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int fa[MAXN];
int deg[MAXN];
int odd[MAXN];
int find(int x){
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
int main(){
    int N, M;
    while(cin >> N >> M){
        for(int i = 1; i <= N; i++){
            fa[i] = i;
            deg[i] = 0;
            odd[i] = 0;
        }
        for(int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
            deg[a]++;
            deg[b]++;
            int x = find(a);
            int y = find(b);
            if(x != y) fa[x] = y;
        }
        for(int i = 1; i <= N; i++){
            if(deg[i] % 2 != 0) odd[find(i)]++;
        }
        vector<char> hasE(N + 1, 0);
        vector<char> done(N + 1, 0);
        for(int i = 1; i <= N; i++){
            if(deg[i] > 0) hasE[find(i)] = 1;
        }
        long long ans = 0;
        for(int i = 1; i <= N; i++){
            int r = find(i);
            if(done[r]) continue;
            done[r] = 1;
            if(!hasE[r]) continue;
            if(odd[r] == 0) ans += 1;
            else ans += odd[r] / 2;
        }
        cout << ans << "\n";
    }
    return 0;
}
Ant Trip

正文

一本通·提高篇的其它内容
