题目

题目描述：
小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：
无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。
可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。

输入描述：
第一行两个整数n，m代表图的点数和边数。
接下来m行，每行两个整数u，v代表u，v有边相连（无向边）

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

解析

首先这道题和题目说的一样就是一道简单的图的遍历：
  • 不过这道题的特点就是有个特殊条件：每次走两步，问我们能不能走完这张图。

我们先来看题：
  1. 题目虽然叫我们遍历图了，但是一下就能发现，他并没有说走过的节点不能再走，所以中间节点是可以走走过的地方的。
  2. 我们都知道一条路下去，如果两步两步一走，绝对是不可能遍历所有节点的，假如起点是偶数节点的话，那你只能走完所有偶数节点。
  3. 为了能有变换，我们就一定要有环结构，才能让奇偶产生变换，而且必须是奇数环。因为奇数环走一圈下来奇偶就换了，而偶数环却不行。
  4. 所以题目就变成了判定有没有奇数环，没有的话加一条边就能造出来。
  5. 这里我们484漏了什么？！
  6. 对了！题目没有告诉我们这到底是不是连通图啊！！所以我们还要加边让这个变成一整张连通图（多一张加一条边）。
  7. 所以题目就变成了：判断信息中有多少张连通图与是否有奇数环。

连通图判定：
  • 这个简单，因为每一次dfs都可以遍历一张图，我们对每个点进行dfs（如果这个点被以前的点遍历过就不进行了）。
  • 遍历过怎么记呢？加一个visited观测数组做标记就好啦。

奇数环判定：
  1. 奇数环的特点是什么呢？当然是奇数咯（废话。
  2. 奇数又有什么特点，这里就要用到经验了，我们可以用一个双色数组标记奇偶节点。
  3. 判定环的奇偶就只要判定遍历完环的时候，相邻的两个点的颜色是否相同就可以了（奇数就是相同，偶数是不同）
  4. 栗子：奇数环假设就是101，首尾相同对不对。偶数环假设是1010，首尾不同对不对。

然后就是打代码了呗：
  1. 首先我们用前向星保存图（老方法了）。
  2. 然后对每个点（要判定以前有没有被遍历过哦）进行dfs。
  3. 最后输出就是联通图数量 - 1 + 是不是奇数环（是就+0，不是就+1构成奇数环）。
  4. 看我代码呗~

AC代码 

#include <iostream>
using namespace std; 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
//代码预处理区 

const int MAX = 1e5 + 7; 
int head[MAX], tot;
struct Node {
    int v, next;
} edge[MAX << 1];
int n, m, ans;//n个点，m条边，加ans条边
bool visited[MAX], color[MAX], flag;//标记数组，奇偶判定数组，奇环判定变量
//全局变量区 

void add_edge(int u, int v);
void dfs(int u, int fa);
//函数预定义区

int main() { 
    IOS;
    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; 
}
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;//奇环判定为true
    }
}
//函数区