图的遍历 题解

呜呜来晚了。。。

题目大意：

你只能两步两步的走,问你最少添加多少条边才可以使得你能遍历完整个图

题解:

我们每次只能两步两步地走，那么如果，我们走一条边再回去，这是毫无意义的。

如果，我们一个图中没有无向边环，（也即是图的形状类似于树），那么，很明显的，一个点到另外一个点走的步数的奇偶性就确定了，而且，必然无法走通，我们就必须考虑添边。

那么要添几条边呢？

我们分析下，我们现在添加一条边后，就必然产生了一个无向边环，那么我们讨论下这个环的奇偶性即可。

如果这个环是偶环，那么，我们走一遍环后，步数奇偶性不变，原来不能到达的点现在还是不能到达，没用。

如果这个环是奇环，那么，我们走一遍环后，步数奇偶性就改变了，原来不能到达的点都可以到达了。

于是，我们只需要添一条边构造出一个奇环就行了。

如果原本就存在奇环的话，就不需要添加奇环了

但是，我们的图并不能保证连通啊，这个怎么办呢？

很简单，我们先添几条边，把图做连通后，再判断图中是否存在奇环即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
struct node{
    int v,nex;
}t[N<<1];
bool col[N];
int len,las[N];bool vis[N],flag=1;//是否没有奇环
inline void add(int u,int v){
    t[++len]=(node){v,las[u]},las[u]=len;
}
inline void dfs(int now){
    vis[now]=1;
    for(int i=las[now];i;i=t[i].nex){
        int v=t[i].v;
        if(vis[v]){
            if(col[v]==col[now])flag=0;
            continue;
        }
        col[v]=(col[now]^1);
        dfs(v);
    }
    return;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    int ans=0;
    dfs(1);
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            ++ans,dfs(i);//添加若干条边使得图连通
        }
    }
    printf("%d",ans+flag);
    return 0;
}