染色法，奇数环判定

为啥一直都没想到染色法有这么多用处呢，，，虽然能很容易写出dfs，但还是题做的少。

环的判定

dfs过程中，若遇到当前正在搜索的点的邻接点已经被搜索过时，则说明存在环！这是适用于无向图的dfs方案，有向图emmm,,貌似也是。

有向图判断环的存在，求环的长度。
图

奇数环

其实奇数环会判断了，偶数环不也一样么，，，
染色法，若一个点的颜色和它的一个邻接点的颜色相同，那么就说明有奇数环存在！
判断偶数环的话，先判断一下是否有环，然后再判断每一个点的颜色和它的邻接点的颜色，若有不冲突的情况，则说明有偶数环。

图的遍历

首先求一下连通块的数量cur，然后答案先加上cur-1，因为要把图连通。然后判断每个连通块中，是否存在奇数环即可，若存在，答案直接输出；否则答案要再加1。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct edge{
    int from, to, next;
}e[maxn*2];
int n, m, tot, cur, flag;
int head[maxn], vis[maxn];
inline void AddEdge(int from, int to){
    tot++;
    e[tot].from = from;
    e[tot].to = to;
    e[tot].next = head[from];
    head[from] = tot;
    return;
}
void dfs(int x, int color){
    vis[x] = color;
    for (int i=head[x];i;i=e[i].next){
        if (!vis[e[i].to])
            dfs(e[i].to, -1*color);
        if (vis[e[i].to]==color)
            flag = 0;
    }
    return;
}
int main(){
    int u, v;
    scanf ("%d %d", &n, &m);
    tot = cur = 0;
    flag = 1;
    for (int i=1;i<=m;i++){
        scanf ("%d %d", &u, &v);
        AddEdge(u, v);
        AddEdge(v, u);
    }
    for (int i=1;i<=n;i++)  if (vis[i]==0){
        cur++;
        dfs(i, 1);
    }
    printf ("%d", cur-1+flag);
    return 0;
}