图的遍历(二分图)

题目：

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

做法：

两步走不难往二分图上想。如果一幅图是二分图，将图分成2个集合。从1出发只能走到1所在集合中的点。而只要该图不是二分图，必定有一条边连接同一个集合中的2个点，进而可以从一个集合走到另一个集合，也就能走完所有点。
所以这题做法是：先求出所有联通块。联通块数量-1条边是必须加的。然后看一下每个联通块是否有非二分图。若有就不需另加边。否则加一条边。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, m, col[N], extra;
vector<int> g[N];
void dfs(int u, int c){
    col[u] = c;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (!col[v]) dfs(v, 3-c);
        if (col[v] == col[u]) extra = 0;
    }
}
int main(void){ 
    IOS;
    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);
    }
    extra = 1;
    int cnt = -1;
    for (int i = 1; i <= n; ++i){
        if (!col[i]){
            dfs(i, 1), cnt++;
        }
    }
    cout << cnt+extra << endl;
    return 0;
}