CF209C Trails and Glades

题目链接

题意

有一个\(n\)个点\(m\)条边的无向图(可能有重边和自环)(不一定联通)。问最少添加多少条边，使得可以从\(1\)号点出发，沿着每条边走一遍之后回到\(1\)号点。

思路

其实就是加最少的边构成欧拉回路。对于度数为奇数的点，与其他度数为奇数的点相连即可。
如果一个联通块中点的度数全部为偶数，那么就需要与其他联通块连\(2\)条边。否则需要连一条。
如果一个点是孤立点，如果没有自环的话就不用管他。如果有自环就要与其他联通块相连。
\(1\)号点即使是孤立点并且没有自环，也要与其他联通块相连。
因为每一条边我们都考虑了两次，所以最后的答案要在上面方法统计出的答案除以\(2\)。
最后如果只有一个联通块，并且点的度数全部为偶数的话，要特判输出\(0\)

代码

/*
* @author: wxyww
* @date: 2019-03-02 22:21:18
* @last modified time: 2019-03-02 22:29:55
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int n = 1000000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int ik[n],du[n],vis[n],ok[n];
vector<int>e[n];
int bz;
void dfs(int u) {
    int k = e[u].size();
    if(du[u] & 1) bz = 1;
    vis[u] = 1;
    for(int i = 0;i < k;++i) {
        int v = e[u][i];
        if(vis[v]) continue;
        dfs(v);
    }
}
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= m;++i) {
        int u = read(),v = read();
        ok[u] = ok[v] = 1;
        if(u == v) continue;
        du[u]++;du[v]++;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    ok[1] = 1;
    int ans = 0,jd = 0,tot = 0;
    for(int i = 1;i <= n;++i) {
        if(du[i] & 1) {
            ans++;
            jd++;
        }
        else if(!vis[i] && ok[i]) {
            bz = 0;
            tot++;
            dfs(i);
            if(!bz) ans+= 2;
        }
    }
    if(tot == 1 && jd == 0) {
        puts("0");return 0;
    }
    cout<<ans / 2;

    return 0;
}