HDU 5215 Cycle(dfs判环)

题意

\(t\)组数据，给出\(n\)个点\(m\)条边的有向图，问是否存在一个奇环/偶环

sol

奇环比较好判断吧，直接判是否是二分图就行了。。

偶环看起来很显然就是如果dfs到一个和他颜色不相同的点，说明出现偶环。

但事实上有一种情况没考虑到。

像这样

显然1 2 4 5会形成一个环

显然该偶环是两个奇环去掉中间的部分构成的。

直接在搜到的奇环上打标记即可，如果一个点被访问了两次，说明存在一个偶环

#pragma comment(linker, "/stack:102400000,102400000") 
#include<bits/stdc++.h>
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first 
#define se second 
using namespace std;
const int maxn = 1e5 + 10, inf = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int t, n, m, vis[maxn], fa[maxn], tag[maxn], anse, anso;
vector<int> v[maxn];
void dfs(int x, int _fa) {
    vis[x] = vis[_fa] ^ 1; fa[x] = _fa;
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i]) == _fa || (tag[to])) continue;
        if(vis[to] == -1) dfs(to, x);
        else if(vis[to] != vis[x]) anse = 1;
        else {
            anso = 1;//二分图染色
            int now = x;
            while((now != to) && (!anse) ) {
                if(tag[now] == 1) {anse = 1;break;}
                tag[now] = 1;
                now = fa[now];
            }
            tag[to] == 1 ? anse = 1 : tag[to] = 1;
        }
    }
}
int solve() {
    n = read(); m = read();
    memset(vis, -1, sizeof(vis)); vis[0] = 1;
    memset(tag, 0, sizeof(tag));
    for(int i = 1; i <= n; i++) v[i].clear(); anse = anso = 0;

    for(int i = 1; i <= m; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
        if(vis[i] == -1) fa[i] = 0, dfs(i, 0);

    puts(anso ? "yes" : "no");
    puts(anse ? "yes" : "no");
}
int main() {
    for(int t = read(); t--; solve());
}
/*
3
3 3
1 2
2 3
3 1
1 0
4 4
1 2
2 3
3 4
4 1
*/