前言:

这是一个很不错的思维题!

思路:

这个题就是要让我们来证明一幅图必须有奇数环,才能使得全图被遍历(假如按2步走的话).
首先我们对于一棵树来说,我们知道假如我们不走到叶子节点再还回肯定是没有意义的,但是其实我们走到叶子节点再还回也是没有意义的.
比方说我们现在有两条链,奇数链和偶数链.
奇数链:1->2,2->3.我们会发现走到叶子节点是没有意义的,无法改变他来时的点的位子.
偶数链:1->2,2->3,3->4.同样的,这里也是没有意义的,1->3,3->3.还是没改变.
好!接下来是偶数环.
偶数环:1->2,2->3,3->4,4->1.无论我们怎么走,来时哪个点,回来时也是哪个点.
但是,奇数环就不一样了~
它直接改变了奇偶性质.综上,我们就证明了.

代码:

用染色法判断奇数环即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int>g[N];
int deg[N],root=0;
int color[N]; 
int odd_circle=1;
void dfs(int u,int col)
{
    if(color[u]!=-1)
    {
        if(color[u]!=col)    odd_circle=0;
        return;
    }color[u]=col;
    for(int x:g[u])    dfs(x,1-col);
}

int main()
{
    memset(color,-1,sizeof color);
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }int ans=-1;
    for(int i=1;i<=n;i++)
    {
        if(color[i]==-1)
        {
            dfs(i,1);ans++;
        }
    }ans+=odd_circle;
    printf("%d\n",ans);
    return 0;
}