【每日一题】【5月21日】图的遍历

题意：

给定无权双向图，顶点数为 ，边数为 。从顶点 开始遍历，每次“走两步”。问最少需要添加多少条边，可以走遍整个图。

解法：

先考虑连通块内的情况：

对顶点进行黑白染色，那么和顶点 颜色相同的点，都可以直接通过原图中的边走到。

然后再考虑从某个点如何“走两步”走到另一个颜色不同的点：若某个顶点的邻接顶点中包含颜色不同的点，那么就可以以这个顶点作为“两步”的中间点，从而做到从一个颜色“走到”另一个颜色。

如果不存在呢？显然必然存在一种颜色的顶点数 ，且存在一条边的两端顶点颜色不一致。那么只需要加一条边，就可以满足上面的情况，及可以走遍整个图。
假设颜色1的顶点数 ，某条边两端顶点为 ，颜色为 ； v，颜色为 。添加的这条边其中一个顶点为 ，另一个顶点为颜色1的其它任一顶点 。则走一步可以从 到 ，或 到 。

然后再考虑连通块之间的情况：
假设连通块数量为 ，显然至少是需要加 条边来使图连通。那么加边的方式改变上面考虑到的情况：即每个连通块都不满足上面的条件，会存在某种加边方式改变使得联通之后满足条件吗？
答案是不会。
这一点按照黑白染色考虑会比较麻烦。
我们换个角度来考虑：奇数环。
若连通块内存在奇数环，显然不加边即可直接遍历。若不存在，则加一条边即可。
在连通块之间加边使其连通，在每个连通块都不存在奇数环的情况下，显然任意的加边方式都不会产生奇数环。

这样这道题的做法就出来了。
统计连通块数量；对每个连通块检查是否存在奇数环（黑白染色下，某个顶点的邻接顶点中有颜色不一致的顶点）。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> G[N];
int col[N], n, m;
void dfs(int u, int c) {
    col[u] = c;
    for(int v : G[u]) if(col[v] == -1) dfs(v, c ^ 1);
}
int main() {
    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);
    }
    memset(col, -1, sizeof col);
    int tot = 0;
    for(int i = 1; i <= n; i++)
        if(col[i] == -1) {
            tot++;
            dfs(i, 0);
        }
    bool flag = false;
    for(int i = 1; i <= n; i++) {
        bool vis[2] = {false, false};
        for(int v : G[i]) vis[col[v]] = true;
        if(vis[0] && vis[1]) flag = true;
    }
    int ans = tot - 1;
    if(!flag) ans++;
    cout << ans << endl;
    return 0;
}