RainAir
My OI Blog
RainAir
HDU 5215 Cycle

题目链接

题目描述

给定一张无向图,判断是否存在奇环和偶环。
$n \leq 100000,m \leq 300000$

题解

这是一个二合一的题目。
首先我们考虑如何判断奇环,注意到一个性质:如果一个图有奇环,那么这个图不能被二分图染色。
那么判断奇环只需要二分图染色一遍就可以了。
我们考虑偶环,有两种情况:第一种就是一个大偶环,第二种是两个或多个奇环拼成的一个偶环。
易证得两个及以上的奇环拼在一起一定会存在偶环。
那么我们在染色的时候顺便记录一下每个点在搜索树上的父亲,找到一个奇环就暴力向上跳并且染色,直到出现重复染色就可以判断偶环了。
第一种偶环情况也很好判断,当一个点访问到从前被遍历过的点的时候如果不矛盾就存在这样一个偶环。
时间复杂度应该是 $O(n+m)$.

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/274
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

HDU 5215 Cycle
题目链接 题目描述 给定一张无向图,判断是否存在奇环和偶环。 $n \leq 100000,m \leq 300000$ 题解 这是一个二合一的题目。 首先我们考虑如何判断奇环,注意到一个性质:如果一个图…
扫描二维码继续阅读
2018-11-21
标签
近期评论