[hdu5215][Cycle]

题目链接

思路

首先可以通过二分图染色找到奇环和一部分偶环。这个比较简单

但是还有一种偶环容易忽略。

如图(别问我为啥没节点4)

第一次可以找到1-2-3-1)这个奇环，第二次可以找到(3-5-6-3)这个奇环。但是(1-2-3-5-6-3-1)这个偶数环就被忽略了。

再一种情况

如图，我们可以找到(1-2-3-4-5-1)这个奇环，也可以找到(3-4-5-6-7-3这个奇环)，但是忽略了(1-2-3-7-6-5-1)这个偶环。

可以证明，只要两个奇数中间有相交部分，那么一定存在一个偶环。因为假设相交部分有偶数条边(如上图),又因为两个环都是奇环，所以每个奇环都会剩下奇数条边。加起来刚好是偶数条边。同样，如果中间部分由奇数条边，那么每个奇环还会剩下偶数条边，加起来刚好也是偶数条边。所以只要能找到两个相交的奇环，那么一定存在一个偶环。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100000+100,M=N*3;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,fa[N],ans[3],head[N],ejs,col[N],ji[N];
struct node {
    int nxt,v;
}e[M];
void add(int u,int v) {
    e[++ejs].v=v;e[ejs].nxt=head[u];head[u]=ejs;
}
void init() {
    ans[2]=ans[1]=0;
    memset(head,0,sizeof(head));
    ejs=0;
    memset(col,-1,sizeof(col));
    memset(ji,0,sizeof(ji));
    memset(fa,0,sizeof(fa));
    n=read();int m=read();
    for(int i=1;i<=m;++i) {
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
}
int Jump(int u,int v) {//标记为奇环 并判断相交 
    for(;u!=v&&u;u = fa[u]) {
        if(ji[u]) return 1;
        ji[u] = 1;
    }
    return 0;
}
void dfs(int u) { 
    for(int i=head[u]; i;i=e[i].nxt) {
        int v = e[i].v;
        if(v == fa[u]) continue;
        if(col[v] == -1) {
            col[v] = col[u]^1;//二分图染色 
            fa[v] = u;
            dfs(v);
        }
        else {
            if(col[v] == col[u]) {
                ans[1] = 1;
                if(Jump(u,v)) ans[2] = 1;//如果两个奇环有相交部分，那么就有偶环 
            }
            else ans[2] = 1;
        }
    }
}
void solve() {
    for(int i=1;i<=n; ++i) {
        if(col[i] == -1) {
            col[i] = 0;
            dfs(i);
        }
    }
    if(ans[1]) puts("YES");
    else puts("NO");
    if(ans[2]) puts("YES");
    else puts("NO");
}
int main() {
    int t=read();
    while(t--) {
        init();
        solve();
    }
    return 0;
}