【题解】图的遍历

感想：看到这个题目一开始没什么想法，因为不知道怎么才能每个点都走得到。后来发现本来是只能走图上的奇数位置点，如果你走一个奇环，就能改变奇偶了，从而可以走偶数个点了。

思路：根据上面说的，如果一个图里存在一个奇环，就能够走完所有的点。但是这个图不一定是连通的，可能有很多个连通分量，所以这些连通分量之间都需要一条边连起来。奇环也同样连一条边就好了。
因此：ans=连通分量个数-1+是否存在奇环(是=0，不是=1)。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

VI edge[maxn];
int dep[maxn];

int flg=1;

void dfs(int u,int fa,int d){
    if(dep[u]){
        if((d>dep[u])&&(d-dep[u])&1) flg=0;
        return ;
    }
    dep[u]=d;
    for(int i=0;i<edge[u].size();i++){
        int to=edge[u][i];
        if(to==fa) continue;
        dfs(to,u,d+1);
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        edge[x].pb(y);edge[y].pb(x);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!dep[i]){
            ans++;
            dfs(i,0,1);
        }
    }
    printf("%d",ans+flg-1);
    return 0;
}