Description

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

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

Solution

首先考虑要完整遍历整个图，需要联通，先 dfs 找到连通块数量 ， 然后把连通块连接起来需要加 条边
其次，这道题他的遍历方式有所不同，他是两步两步走，那么如果存在一个奇数环，我们可以通过走这个环来调节
使得我们总能到达每个点，那么我们可以先找下是否存在奇数环，如果存在，答案就是
否则我们加一条边构造一个奇数环, 答案为
这里学到一个找奇数环的技巧，通过染色后如果发现环上相邻两点颜色相同
则这个环是奇数环

Code

#include<iostream>
#include<vector>

using namespace std;
const int N = 1e5 + 5;

vector<int> G[N];
bool vis[N], p[N], flag;

void dfs(int u) {
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(!vis[v]) {
            vis[v] = 1;
            p[v] = !p[u];
            dfs(v);
        } else if(p[v] == p[u]) {
            flag = 1;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);        
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            vis[i] = 1;
            p[i] = 1;
            ans++;
            dfs(i);
        }
    }
    if(flag) {
        cout << ans - 1 << "\n";
    }    else {
        cout << ans << "\n";
    }
    return 0;
}