题意

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

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

分析

首先假设这个图是个连通图。
那么如果这个图有一个奇数大小的环，这个图的所有点一定可以被访问到。（因为可以在环上进行调整）
如果这个图不是连通图，那我们要先加边使它连通，那么原来如果有一个连通块满足全部点可以访问到，整个图一定都可以访问到。
所以我们现在就把问题转化为：求图上是否有一个奇数大小的环。
这个问题是可以用 来判断的。
最后复杂度是 的。

有个小问题

如果题目问的是图上是否有偶数大小的环，能否进行判断呢？？

代码如下

#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
struct node{
    int a, b, n;
}d[N * 2];
int h[N], v[N], cnt, ans, flag = 1;
void cr(int a, int b){
    d[++cnt].a = a;  d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
    int i, b;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(!v[b]){
            v[b] = v[a] + 1;
            dfs(b);
        }
        else if((v[a] - v[b] + 1) % 2) flag = 0;
    }
}
int main(){
    int i, j, n, m, a, b;
    n = read(); m = read();
    for(i = 1; i <= m; i++){
        a = read(); b = read();
        cr(a, b); cr(b, a);
    }
    for(i = 1; i <= n; i++) if(!v[i]) dfs(i), ans++;
    printf("%d", ans - 1 + flag);
    return 0;
}