经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
HDU 5215 Cycle(dfs判环)
来源:cnblogs  作者:自为风月马前卒  时间:2018/10/15 9:27:05  对本文有异议

题意

题目链接

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

Sol

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

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

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

像这样

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

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

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

  1. #pragma comment(linker, "/STACK:102400000,102400000")
  2. #include<bits/stdc++.h>
  3. #define Pair pair<int, int>
  4. #define MP(x, y) make_pair(x, y)
  5. #define fi first
  6. #define se second
  7. using namespace std;
  8. const int MAXN = 1e5 + 10, INF = 1e9 + 7;
  9. inline int read() {
  10. char c = getchar(); int x = 0, f = 1;
  11. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  12. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  13. return x * f;
  14. }
  15. int T, N, M, vis[MAXN], fa[MAXN], tag[MAXN], anse, anso;
  16. vector<int> v[MAXN];
  17. void dfs(int x, int _fa) {
  18. vis[x] = vis[_fa] ^ 1; fa[x] = _fa;
  19. for(int i = 0, to; i < v[x].size(); i++) {
  20. if((to = v[x][i]) == _fa || (tag[to])) continue;
  21. if(vis[to] == -1) dfs(to, x);
  22. else if(vis[to] != vis[x]) anse = 1;
  23. else {
  24. anso = 1;//二分图染色
  25. int now = x;
  26. while((now != to) && (!anse) ) {
  27. if(tag[now] == 1) {anse = 1;break;}
  28. tag[now] = 1;
  29. now = fa[now];
  30. }
  31. tag[to] == 1 ? anse = 1 : tag[to] = 1;
  32. }
  33. }
  34. }
  35. int solve() {
  36. N = read(); M = read();
  37. memset(vis, -1, sizeof(vis)); vis[0] = 1;
  38. memset(tag, 0, sizeof(tag));
  39. for(int i = 1; i <= N; i++) v[i].clear(); anse = anso = 0;
  40. for(int i = 1; i <= M; i++) {
  41. int x = read(), y = read();
  42. v[x].push_back(y); v[y].push_back(x);
  43. }
  44. for(int i = 1; i <= N; i++)
  45. if(vis[i] == -1) fa[i] = 0, dfs(i, 0);
  46. puts(anso ? "YES" : "NO");
  47. puts(anse ? "YES" : "NO");
  48. }
  49. int main() {
  50. for(int T = read(); T--; solve());
  51. }
  52. /*
  53. 3
  54. 3 3
  55. 1 2
  56. 2 3
  57. 3 1
  58. 1 0
  59. 4 4
  60. 1 2
  61. 2 3
  62. 3 4
  63. 4 1
  64. */
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号