题目描述
小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：

无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。

输入描述:
第一行两个整数n，m代表图的点数和边数。

接下来m行，每行两个整数u，v代表u，v有边相连（无向边）
输出描述:
输出一行，代表最少要添加的边数。

思路：
先不考虑走两步，就先考虑要走完整个图，那么整个图肯定是需要联通的，那么我们需要求出有多少个连通块，需要加的边数就是连通块个数-1，这样先保证图联通。
图联通后再考虑走两步的走法，可以简单画一下，如果图联通，只要存在奇数环，那么就可以走完整个图，因为奇数环，从环的起点走到环的终点后，从终点继续走另一边到起点，这样之前遍历的是奇数点，第二次过来就变成了偶数点，不太明白的话，可以画图理解下。
那么如果没有奇数环呢?只需要在其中一个连通块中，加上一条边形成奇数环即可。
所以整个题等价求有多少个联通块、求是否存在奇数环
那么可以通过dfs ，O(m+n)复杂度即可解决。

#include<bits/stdc++.h>
using namespace std;
vector<int> e[100005];
int ans,flag=1;///flag=1 表示不存在奇数环
int v[100005];
void dfs(int x){

    for(auto &it:e[x]){
        if(v[it]==-1){//没被染色
            v[it]=v[x]^1;///相邻的点染相反的颜色
            dfs(it);
        }
        else if(v[it]==v[x]) flag=0;//相邻的点已被染色，并且颜色相同  说明有奇环
    }
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    memset(v,-1,sizeof v);
    for(int i=1;i<=n;i++){
        if(v[i]==-1){
            ans++;//联通块个数
            v[i]=0;//进行染色
            dfs(i);
        }
    }
    cout<<ans-1+flag;
    return 0;
}