HDU-5215 Cycle 无向图判奇环偶环

题意：给一个无向图，判断这个图是否存在奇环和偶环。

解法：网上有一种只用dfs就能做的解法，但是我不太理解。

这里用的是比较复杂的。首先奇环很简单可以用二分图染色判断。问题是偶环怎么判断？这里我们想，一旦有两个环共享了一些点，那么这两个环一定能组成一个偶环。

那么我们考虑tarjan找出所有桥删去，那么对于一个边双联通分量，这个边双只要有多于一个环就必定存在偶环。即当且仅当这个边双为一个奇环的情况下才不存在偶环，其他情况都会有偶环。

所以一旦这个边双不是单环，就必定存在偶环。

那么怎么判断这个是不是一单个环呢？点数=边数的时候就是一个单环。

细节详见代码：

#pragma comment(linker,"/STACK:102400000,102400000")

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+;

int n,m,ver,edge,odd,even,col[N];

bool bridge[N];

int cnt=,head[N<<],nxt[N<<],to[N<<];

void add_edge(int x,int y) {

    nxt[++cnt]=head[x]; to[cnt]=y; head[x]=cnt;

}

int num,low[N],dfn[N];

void tarjan(int x,int in) {

    dfn[x]=low[x]=++num;

    for (int i=head[x];i;i=nxt[i]) {

        int y=to[i];

        if (!dfn[y]) {

            tarjan(y,i);

            low[x]=min(low[x],low[y]);

            if (low[y]>dfn[x])

                bridge[i]=bridge[i^]=;

        } else if (i!=(in^))

            low[x]=min(low[x],dfn[y]);

    }

}

void dfs(int x,int fa) {

    col[x]=-col[fa]; ver++;

    for (int i=head[x];i;i=nxt[i]) {

        if (bridge[i]) continue;

        int y=to[i]; edge++;

        if (y==fa) continue;

        if (!col[y]) dfs(y,x);

        else if (col[x]==col[y]) odd=; else even=;  //染色过程判断奇偶环

    }

}

int main()

{

    int T; cin>>T;

    while (T--) {

        cin>>n>>m;

        cnt=; for (int i=;i<=n;i++) head[i]=;

        for (int i=;i<=m;i++) {

            int x,y; scanf("%d%d",&x,&y);

            add_edge(x,y); add_edge(y,x);

        }

        num=; for (int i=;i<=n;i++) dfn[i]=low[i]=;

        for (int i=;i<=n;i++)

            if (!dfn[i]) tarjan(i,);  //找桥

        odd=even=;

        for (int i=;i<=n;i++) col[i]=; col[]=;

        for (int i=;i<=n;i++)

            if (!col[i]) {

                ver=; edge=;

                dfs(i,);

                if (ver> && edge/!=ver) even=; //点数和边数不等，存在偶环

            }

        printf("%s\n",odd?"YES":"NO");

        printf("%s\n",even?"YES":"NO");

        for (int i=;i<=cnt;i++) bridge[i]=;

    }

    return ;

}