题目链接

<h1>题目描述</h1>

给定一张无向图，判断是否存在奇环和偶环。
$n \leq 100000,m \leq 300000$

<h1>题解</h1>

这是一个二合一的题目。
首先我们考虑如何判断奇环，注意到一个性质：如果一个图有奇环，那么这个图不能被二分图染色。
那么判断奇环只需要二分图染色一遍就可以了。
我们考虑偶环，有两种情况：第一种就是一个大偶环，第二种是两个或多个奇环拼成的一个偶环。
易证得两个及以上的奇环拼在一起一定会存在偶环。
那么我们在染色的时候顺便记录一下每个点在搜索树上的父亲，找到一个奇环就暴力向上跳并且染色，直到出现重复染色就可以判断偶环了。
第一种偶环情况也很好判断，当一个点访问到从前被遍历过的点的时候如果不矛盾就存在这样一个偶环。
时间复杂度应该是 $O(n+m)$.

<h1>代码</h1>

// 这里的 read(x) 本来是一个 fread 快读函数的被我删了qwq
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100000+5;
const int MAXM = 300000+5;

struct Node{
    struct Edge *firstEdge;
    Node *fa;
    int col;
    bool vis;
}node[MAXN];

struct Edge{
    Node s,t;
    Edge *next;
}pool[MAXM<<1],*frog = pool;

Edge New(Node s,Node *t){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v){
    node[u].firstEdge = New(&node[u],&node[v]);
    node[v].firstEdge = New(&node[v],&node[u]);
}

int N,M,ts;
bool odd,even;

inline void prework(){
    CLR(pool,0);frog = pool;
    FOR(i,1,N) node[i].firstEdge = NULL,node[i].col = 0,node[i].fa = NULL,node[i].vis = false;
    even = odd = false;
}

bool calc(Node x,Node y){
    while(x != y){
        if(!x) return false;
        if(x->vis) return true;
        x->vis = true;
        x = x->fa;
    }
    return false;
}

void dfs(Node *v){
    for(Edge *e = v->firstEdge;e;e = e->next){
        if(e->t == v->fa) continue;
        if(!e->t->col){
            e->t->col = 3-v->col;
            e->t->fa = v;
            dfs(e->t);
        }
        else{
            if(e->t->col == v->col){
                odd = true;
                if(calc(v,e->t)) even = true;
            }
            else even = true;
        }
    }
}

inline void Solve(){
    read(N);read(M);
    prework();
    FOR(i,1,M){
        int u,v;read(u);read(v);
        add(u,v);
    }
    FOR(i,1,N) if(!node[i].col) node[i].col = 1,dfs(&node[i]);
    puts(odd ? "YES" : "NO");
    puts(even ? "YES" : "NO");
}

int main(){
    int T;read(T);
    while(T--) Solve();
    system("pause");
    return 0;
}