HDU 5215 Cycle(dfs判环)
程序员文章站
2023-02-18 18:23:25
题意 "题目链接" $T$组数据,给出$n$个点$m$条边的有向图,问是否存在一个奇环/偶环 Sol 奇环比较好判断吧,直接判是否是二分图就行了。。 偶环看起来很显然就是如果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 */
上一篇: 黄油是什么,黄油怎么制作的呢?