题意

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

输入描述

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

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

输出描述

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

解析

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

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

代码

#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; 
}