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

*/

巴特西

HDU 5215 Cycle(dfs判环)

题意

Sol

最新文章

热门文章