图的遍历

对于一个奇数环，总能遍历环上每个点；
首先，判断图是不是连通，即有几个连通块，那么边数=连通块数-1；
判断一下是否有奇数环，最后没有奇数环+1即可；（画个图试一下）

#include<bits/stdc++.h>
using namespace std;
const int maxn=110000;
int head[maxn],cnt,tag=1,vis[maxn],ans;
struct edge{
    int nx,to;
}edge[maxn*2];
void add(int u,int v)
{
    edge[++cnt].nx=head[u];
    edge[cnt].to=v;
    head[u]=cnt;
}
void dfs(int x)
{
    for(int i=head[x];i;i=edge[i].nx)
    {
        int v=edge[i].to;
        if(vis[v]!=-1){
            if(vis[v]==vis[x]) tag=0;//相邻点颜色一样，就说明是奇数环。
        }
        else {
            vis[v]=vis[x]^1;dfs(v);//染色部分
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    memset(vis,-1,sizeof(vis));
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==-1)//判断连通块个数
        {
            ans++;
            vis[i]=0;
            dfs(i);
        }
    }
    cout<<ans-1+tag;
}