欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HDU 5215 Cycle(dfs判环)

程序员文章站 2023-02-18 18:23:25
题意 "题目链接" $T$组数据,给出$n$个点$m$条边的有向图,问是否存在一个奇环/偶环 Sol 奇环比较好判断吧,直接判是否是二分图就行了。。 偶环看起来很显然就是如果dfs到一个和他颜色不相同的点,说明出现偶环。 但事实上有一种情况没考虑到。 像这样 显然 会形成一个环 显然该偶环是两个奇环 ......

题意

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

sol

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

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

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

像这样

HDU 5215 Cycle(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
*/