图的遍历

从1开始走，每次走两步，给定一个图，求最少加多少边，让整个图每个点都可以被遍历。
思路：
奇数环可以改变走的次序，然后整个图要联通，所以先把联通块变成树，如果存在奇数环那就不用加1，不存在再加1构造出奇数环就可以了～

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
#define int long long
const int N=1000010,M=2020;
int a[N];
//vector<pair<int,int>>v;
vector<int>v[N];
const int mod=1000000007; 
int qmi(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)    res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
//int c[2020][2020];
int fact[N+M];

int c(int a,int b)
{
    return fact[a]*qmi(fact[a-b],mod-2)%mod*qmi(fact[b],mod-2)%mod;
}
int vis[N];
bool flag=1;
void dfs(int u,int c)
{
    vis[u]=c;    
    for(auto j:v[u])
    {
        if(!vis[j])
            dfs(j,3-c);
        else
        {
            if(vis[j]==vis[u])
            {
                flag=0;
            }
        }
    }
}
signed main()
{
    int n;
    cin>>n;
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            res++;
            dfs(i,1);
        }
    }
    cout<<res+flag-1<<endl;
    return 0;
}