NC52275

感受
噫，怎么这么少人过？难道很难，不如先看看再说。
读完题，怎么没思路，简单想一下，如果图是连通的，那么怎样可以保证一定遍历完呢？
画一画，这不是so easy吗。那如果有其他连通分量，怎么弄呢？噢噢，这样弄这样弄。
恍然大悟，这不就是xx题吗？

思路
先考虑简单版问题：保证图的连通性（也就是从1遍历，可以访问任意点），怎么解决呢？
多画画，就会发现，如果图中存在奇环，那么一定有一条路径使得从1经过那个奇环到达1的儿子节点。
也就是说，存在奇环就保证我们既可以从1节点“走两步”，也可以从1的儿子节点“走两步”，这样显然可以遍历整张图。
所以，存在奇环时，ans = 0；不存在奇环时，ans = 1（构造奇环即可）；

不存在奇环一定不可以吗？存在偶环可以吗？----自己画画图就知道不可以了

再考虑这个问题，如果存在其他连通分量呢？
对于每一个连通分量，我们让顶点1与连通分量的其中一个点连边，这样这个点的儿子就可以“走两步”。
又知道可以从1的儿子节点“走两步”，这样这个点就可以“走两步”。
也就是说，这样构造可以保证我们既可以从该点“走两步”，也可以从该点的儿子节点“走两步”，这样显然可以遍历整个连通分量。

因此ans = 联通分量数 - 1 + （存在奇环时，+0；不存在奇环时，+1）；

代码细节
求联通分量数目？
dfs整张图即可，类似dfs染色

判断有无奇环

愉快地AC吧

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
struct edge{
    int v, nex;
}e[maxn << 1];
int head[maxn], cnt, dep[maxn];
bool vis[maxn];
int n, m;
void add_edge(int u, int v){
    e[++cnt] = (edge){v, head[u]};
    head[u] = cnt;
}
int ans;
void dfs1(int u){
    vis[u] = true;
    int v;
    for(int i = head[u]; i > 0; i = e[i].nex){
        v = e[i].v;
        if(vis[v]) continue;
        dfs1(v);
    }
}
bool has;
void dfs2(int u, int d){
    vis[u] = true; dep[u] = d;
    int v;
    for(int i = head[u]; i > 0; i = e[i].nex){
        v = e[i].v;
        if(vis[v]){
            if((dep[u] - dep[v] + 1) & 1) has = true;
            continue;
        }
        dfs2(v, d + 1);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    int u, v;
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }

    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            ans++;
            dfs1(i);
        }
    }
    ans--;///连通块个数 - 1
    memset(vis, false, sizeof(vis));

    dfs2(1, 1);
    if(!has) ans++;
    printf("%d\n", ans);
    return 0;
}