题意

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

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

输入描述

第一行两个整数n，m代表图的点数和边数。

接下来m行，每行两个整数u，v代表u，v有边相连（无向边）

输出描述

输出一行，代表最少要添加的边数。

解析

要遍历所有的点肯定要所有点都相连，所以如果边数小于n-1就要先补上几条边让他们相连，好，现在我们一点一点来分析，假设所有的点在一条直线上，可以是部分点在一条直线上，

所以很明显，如果点之间是一条直线相连，就无法做到遍历，我们再看成环，

这里我们就可以看出来只有当点数为奇数且成环的时候我们才能做到遍历所有的点，所以如果是一条直线，那么我们将首尾相连，如果成偶数的环，我们在中间加一条线，这样就可以分割成两个奇数的环，

代码

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 7; 
int head[MAX], tot;
struct Node {
    int v, next;
} edge[MAX << 1];
int n, m, ans;
bool visited[MAX], color[MAX], flag;

void add_edge(int u, int v) {
    tot++;
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    visited[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (!visited[v]) {
            color[v] = !color[u];
            dfs(v, u);
        }
        else
            if (color[v] == color[u]) flag = true;
    }
}
int main(void) { 
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!visited[i]) {
            ans++;
            color[i] = true;
            dfs(i, 0);
        }
    cout << ans - 1 + !flag << endl;
    return 0; 
}