图的遍历

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

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

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

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

题解
保证整个图肯定是需要联通的，那么我们需要求出有多少个连通块，需要加的边数就是连通块个数-1。
如果图联通，只要存在奇数环，那么就可以走完整个图，因为奇数环，从环的起点走到环的终点后，从终点继续走另一边到起点，这样之前遍历的是奇数点，第二次过来就变成了偶数点。其实就是判断这个图是不是二分图，用染色法即可。如果没有奇数环，只需要在其中一个连通块中，加上一条边形成奇数环即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
vector<int> v[N];//图的表示
int n,m,color[N],f;
void dfs(int x,int c){
    color[x]=c;//顶点x染成c
    for (int i = 0; i < v[x].size(); ++i){
        if(color[v[x][i]]==c)f=0;
        else if(!color[v[x][i]])dfs(v[x][i],-c);
    }
}
void solve(){
    //如果是连通图，则一次dfs即可访问所有位置
    int k=0,num=0;
    for (int i = 1; i <= n; ++i){
        if (color[i]==0){
            f=1;
            dfs(i,1);
            if(!f)k=1;
            num++;
        }
    }
    if(k)cout<<num-1;
    else cout<<num;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        v[x].push_back(y),v[y].push_back(x);
    }
    solve();
    return 0;
}