[hdu5215][Cycle]
程序员文章站
2022-04-06 13:03:00
hdu5215 思路 首先可以通过二分图染色找到奇环和一部分偶环。这个比较简单 但是还有一种偶环容易忽略。 如图(别问我为啥没节点4) 第一次可以找到1 2 3 1)这个奇环,第二次可以找到(3 5 6 3)这个奇环。但是(1 2 3 5 6 3 1)这个偶数环就被忽略了。 再一种情况 如图,我们可 ......
思路
首先可以通过二分图染色找到奇环和一部分偶环。这个比较简单
但是还有一种偶环容易忽略。
如图(别问我为啥没节点4)
第一次可以找到1-2-3-1)这个奇环,第二次可以找到(3-5-6-3)这个奇环。但是(1-2-3-5-6-3-1)这个偶数环就被忽略了。
再一种情况
如图,我们可以找到(1-2-3-4-5-1)这个奇环,也可以找到(3-4-5-6-7-3这个奇环),但是忽略了(1-2-3-7-6-5-1)这个偶环。
可以证明,只要两个奇数中间有相交部分,那么一定存在一个偶环。因为假设相交部分有偶数条边(如上图),又因为两个环都是奇环,所以每个奇环都会剩下奇数条边。加起来刚好是偶数条边。同样,如果中间部分由奇数条边,那么每个奇环还会剩下偶数条边,加起来刚好也是偶数条边。所以只要能找到两个相交的奇环,那么一定存在一个偶环。
代码
#include<cstdio> #include<cstring> #include<iostream> using namespace std; typedef long long ll; const int n=100000+100,m=n*3; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=x*10+c-'0'; c=getchar(); } return x*f; } int n,fa[n],ans[3],head[n],ejs,col[n],ji[n]; struct node { int nxt,v; }e[m]; void add(int u,int v) { e[++ejs].v=v;e[ejs].nxt=head[u];head[u]=ejs; } void init() { ans[2]=ans[1]=0; memset(head,0,sizeof(head)); ejs=0; memset(col,-1,sizeof(col)); memset(ji,0,sizeof(ji)); memset(fa,0,sizeof(fa)); n=read();int m=read(); for(int i=1;i<=m;++i) { int u=read(),v=read(); add(u,v);add(v,u); } } int jump(int u,int v) {//标记为奇环 并判断相交 for(;u!=v&&u;u = fa[u]) { if(ji[u]) return 1; ji[u] = 1; } return 0; } void dfs(int u) { for(int i=head[u]; i;i=e[i].nxt) { int v = e[i].v; if(v == fa[u]) continue; if(col[v] == -1) { col[v] = col[u]^1;//二分图染色 fa[v] = u; dfs(v); } else { if(col[v] == col[u]) { ans[1] = 1; if(jump(u,v)) ans[2] = 1;//如果两个奇环有相交部分,那么就有偶环 } else ans[2] = 1; } } } void solve() { for(int i=1;i<=n; ++i) { if(col[i] == -1) { col[i] = 0; dfs(i); } } if(ans[1]) puts("yes"); else puts("no"); if(ans[2]) puts("yes"); else puts("no"); } int main() { int t=read(); while(t--) { init(); solve(); } return 0; }
上一篇: dubbo源码(章节一) -- 从日志开始探索dubbo的架构原理
下一篇: 有本事别来两元店装啊!
推荐阅读
-
学习RxJS之JavaScript框架Cycle.js
-
jQuery图片切换插件jquery.cycle.js使用示例
-
HDU 5215 Cycle(dfs判环)
-
net.sf.json.JSONException: There is a cycle in the hierarchy!
-
详解golang避免循环import问题(“import cycle not allowed”)
-
理解ADF Faces Life Cycle
-
PAT 甲级 1122. Hamiltonian Cycle (25)
-
【PAT】1122. Hamiltonian Cycle (25)
-
PAT甲1122 Hamiltonian Cycle(25 分)
-
[Python](PAT)1122 Hamiltonian Cycle(25 分)