bfs\dfs

题意：

链接：https://ac.nowcoder.com/acm/problem/52275
来源：牛客网

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

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

输入描述:
第一行两个整数n，m代表图的点数和边数。

接下来m行，每行两个整数u，v代表u，v有边相连（无向边）
输出描述:
输出一行，代表最少要添加的边数。
示例1
输入
复制
5 4
1 2
2 3
3 4
4 5
输出
复制
1
示例2
输入
复制
5 5
1 2
2 3
3 4
4 5
1 5
输出
复制
0
备注:
数据范围：
3\leq n\leq1e5, \ 2\leq m\leq 1e53≤n≤1e5, 2≤m≤1e5
1\leq u,v\leq n1≤u,v≤n
图中点的编号从1到n。

走两步的意思：
比如现在有两条边：(1,2),(2,3)，从1开始走，只能走到1或者3。
(1->2->3),(1->2->1)

分析

首先，给出结论：对于一个连通块如果则个连通块中有奇数环，那么两步一跳我们就可以到任何一个节点上。
真其实是很明显的，因为我们可以靠那个奇数环来调整步骤。

那么重点便是放在如何判断这个有奇数环，和这个图中有几个连通块
ans = 连通块数-1+[没有奇数环]
我们可以通过加上一条边形成奇数环。

有几个连通块：
我们需要将这些连通块用最少的边连接起来(这些连起来的边并不影响后面的奇数环)
即利用dfs或者bfs进行搜索。

如何判断一个连通块是否有奇数环》
黑白染色法
对于一个偶数环：
1>>2>>3>>4>>5>>6>>1
我们从1开始
1白，2黑，3白，4黑，5白，6黑，1白
我们会发现最终1还是白的
如果是一个奇数环
1>>2>>3>>4>>5>>1
1白，2黑，3白，4黑，5白，1黑
前后相反了，我们可以利用这一特性进行甄别。
根据，算法特点我们很容易想用dfs对不对，但是我们也可以用bfs的，仔细想想是可以的
如果世隔奇数环，那么到一个点的步数肯定既有奇数步的情况也有偶数步的情况。
这里推荐bfs，因为在一些其他的题中bfs还可以用来求解最小奇数环

代码如下、注意细节

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
using namespace std;
const int max_n = 1e5 + 100;
int n, m;
int vis[max_n];
bool flag = true;
vector<int> G[max_n];
int V;

int change(int num) { if (num == 1)return 2;return 1; }

void bfs(int n) {
    vis[n] = 1;
    deque<int> que;que.push_back(n);
    while (!que.empty()) {
        int cur = que.front();que.pop_front();
        for (int i = 0;i < G[cur].size();i++) {
            int now = G[cur][i];
            if (vis[now]) {
                if (vis[now] != change(vis[cur]))flag = false;
                continue;
            }vis[now] = change(vis[cur]);
            que.push_back(now);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;int u, v;
    for (int i = 0;i < m;i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1;i <= n;i++) {
        if (!vis[i]) {
            V++;
            bfs(i);
        }
    }
    cout << V - 1 + flag << endl;
}

在这里，bfs还是有些讲究的（尤其是染色的时机），容易写错