图的遍历

图的遍历：[https://ac.nowcoder.com/acm/problem/52275]

解题思路：
首先容易想到是如果是一个奇数环，那么该环上任意一点都可以被经过，因为gcd(2，奇数)==1,所以延申一下与奇数环连接的所有点也可以被经过，因为可以通过环上的的点来调节（可以选择后退一步），所以如果有奇数环答案就是联通块的数量减1；
如果没有联通块，通过奇数环的理解，我们只需要构造一个可以任意到达的环即可，所以这个时候要多加一条边，所以此时答案就是联通块的个数。
连通块的个数可以用Tarjan求也可以用染色法（标记）,因为要求奇数环，所以染色更简单一点。

代码如下：

#include<bits/stdc++.h>
#define LL long long
#define all(x) (x).begin(),(x).end()
#define le(x) ((int)(x).size())
#define pii pair<int,int>
#define PII pair<LL,LL>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define db printf("Here!\n");
using namespace std;
const double eps=1e-8;
const double Pi=4.0*atan(1.0);
const LL inf=1e14+10;
const int N=2e5+5;
const int M=2e6+5;
const int mod=1e9+7;
//mt19937 rnd(time(0)),shuffle(a+1,a+1+n,rnd);
int n,m,k,t,T,len,op,x,y,z;
int head[N],nxt[N],to[N],col[N],ok;
void add(int x,int y){
    nxt[++T]=head[x];head[x]=T;to[T]=y;
}
void dfs(int now,int v){
    for(int i=head[now];i;i=nxt[i]){
        int u=to[i];
        if(u==now)continue;
        if(col[u]!=-1){
            if(col[u]==v)ok=1;//如果存在相邻两个颜色相同说明存在奇数环
            continue;
        }
        col[u]=v^1;
        dfs(u,v^1);
    }
}
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)col[i]=-1;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(col[i]==-1){
            col[i]=0;
            dfs(i,0);
            k++;
        }
    }
    printf("%d\n",ok?k-1:k);
}
int main(){
    //int o;scanf("%d",&o);
    //while(o--){
        solve();
    //}
    return 0;
}