牛客——图的遍历（dfs染色）

题意：

一次走两步 问最少添加几条边 可以完整的遍历整张图

思路：

考虑环的奇偶性。

如果有奇环，那么从奇环的任意点出发，一定能够走完这个环。

所以如果存在某个连通块是奇环，那么就只需要把剩下的连通块都连接到该连通块上即可，所需要的添加边数就是连通块数-1；

如果不存在奇环的话，先要将某个连通块变成奇环，增加一条边即可，然后再按照上述思路，所需要添加的边数就是连通块数-1+1，即连通块数。

当存在某个连通块是奇环时，我们来考虑剩下的连通块。其中如果有连通块是奇环的话，可以不予考虑，因为一定可以走完。只考虑连通块是偶环（不知道有没有这个词emm）的个数cnt。无论cnt是奇数还是偶数，偶数相加一定是偶数，所以再加上之前的奇环的连通块，就一定是奇数，所以是相当于构成了一个奇环，是可以走完的。

判断奇环染色的原理就类似于二分图染色，dfs即可。具体的就看一下代码叭。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;

vector<int>e[maxn];
int col[maxn];
bool flag=0;//是否存在奇环

void dfs(int color,int u){
    col[u]=color;
    for(auto it:e[u]){
        if(!col[it]) dfs(3-color,it);
        else if(col[u]==col[it]) flag=1;
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        ///无向图
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int res=0;
    for(int i=1;i<=n;i++)
        if(!col[i]) dfs(1,i),res++;
    if(flag) cout<<res-1<<endl;
    else cout<<res<<endl;
    return 0;
}