题目:http://codeforces.com/contest/19/problem/E

先把图连成一棵树,然后对于每条非树边,判断它是在奇环中还是偶环中;

把环上的点打上相应的差分标记,并记录有多少个奇环;

dfs 出来后判断,若没有奇环,那么所有边都可以删;

若有奇环 k 个,遍历边,在 k 个奇环中而不在偶环中的边可以删;

如果一条边既在奇环中又在偶环中,那么若删掉它,原来的一奇环一偶环会合并成一个大奇环,所以这种边不能删;

写、调了整整两小时,改了许多冗余的地方和错误的地方才终于A了,我这代码能力...

码力++!

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=2e4+;
int n,m,fa[maxn],sf[maxn],sg[maxn],g[maxn],f[maxn],ans[maxn],ns;
int col[maxn],hd[maxn],ct,cnt,qhd[maxn],numj;
bool vis[maxn];
struct N{
int to,nxt,edge;
N(int t=,int n=,int e=):to(t),nxt(n),edge(e) {}
}ed[maxn<<],q[maxn];
struct T{
int ff,gg;
T(int f=,int g=):ff(f),gg(g) {}
};
inline int rd()
{
int ret=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return ret*f;
}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void add(int x,int y,int e){ed[++ct]=N(y,hd[x],e); hd[x]=ct;}
inline void ad(int x,int y,int e){q[++cnt]=N(y,qhd[x],e); qhd[x]=cnt;}
inline void dfs2(int x,int pre)
{
vis[x]=; col[x]=!col[pre];
for(register int i=qhd[x];i;i=q[i].nxt)
{
int u=q[i].to;
if(!vis[u])continue;
int lca=find(u);
if(col[u]==col[x])
{
// f[u]++,f[i]++,f[pr[lca]]-=2,numj++;
f[u]++,f[x]++,f[lca]-=,numj++;
sf[q[i].edge]=;
}
else
{
// g[u]++,g[i]++,g[pr[lca]]-=2,numo++;
g[u]++,g[x]++,g[lca]-=;
}
}
for(register int i=hd[x],u;i;i=ed[i].nxt)
if((u=ed[i].to)!=pre)dfs2(u,x);
fa[x]=pre;
}
inline T dfs3(int x,int pre)
{
int smf=f[x],smg=g[x]; vis[x]=;//smf,smg!=0!!!
for(register int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==pre)continue;
T k=dfs3(u,x);int e=ed[i].edge;
sf[e]=k.ff; sg[e]=k.gg;
smf+=k.ff; smg+=k.gg;
}
return T(smf,smg);
}
int main()
{
n=rd(); m=rd();
for(register int i=;i<=n;i++)fa[i]=i;
for(register int i=,u,v;i<=m;i++)
{
u=rd(); v=rd();
if(find(u)!=find(v))
{
fa[find(u)]=find(v);
add(u,v,i); add(v,u,i);
}
else ad(u,v,i),ad(v,u,i);
}
for(register int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=n;i++)if(!vis[i])dfs2(i,);//不仅dfs(1,0)
memset(vis,,sizeof vis);
if(!numj)
{
printf("%d\n",m);
for(int i=;i<=m;i++)printf("%d ",i);
return ;
}
for(int i=;i<=n;i++)if(!vis[i])dfs3(i,);
memset(vis,,sizeof vis);
for(register int i=;i<=m;i++)
if(sf[i]==numj&&!sg[i])ans[++ns]=i;
printf("%d\n",ns);
sort(ans+,ans+ns+);
for(register int i=;i<=ns;i++)printf("%d ",ans[i]);
return ;
}

最新文章

  1. neutron中创建子网时禁用dhcp服务的问题
  2. css中的浮动以及清除浮动
  3. 手机刷机软件与ROM的盈利模式分析
  4. Nginx 开启PATHINFO支持ThinkPHP框架实例
  5. C++头文件中预编译宏的目的
  6. Extjs 4 chart自定义坐标轴刻度
  7. Javascript实现打字效果
  8. NOIP2012模拟试题【奶牛晒衣服】
  9. Windows Phone 8初学者开发—第1部分:系列介绍
  10. C# 经典入门12章-System.Collections.Generic命名空间
  11. cloneNode和replaceChild
  12. C++因继承引发的隐藏与重写
  13. C#中的虚函数及继承关系
  14. 【python 3】 字典方法操作汇总
  15. 02-第一个JavaScript代码
  16. js判断登陆用户名及密码是否为空的简单实例
  17. ELK+Filebeat+Kafka+ZooKeeper 构建海量日志分析平台
  18. laravel响应的发送和程序终止
  19. 安全测试8_Web安全实战1(DVWA部署)
  20. ip黑白名单防火墙frdev的原理与实现

热门文章

  1. Redis系列(五)--主从复制
  2. ThinkPHP---thinkphp模型(M)
  3. springAOP源码解析-190313
  4. 大理石在哪儿(Where is the Marble?,Uva 10474)
  5. pygame 方块随机飞舞动画
  6. Django REST framework 数据处理api
  7. CCF201709-1 打酱油 java(100分)
  8. 常用的HTTP测试工具谷歌浏览器插件汇总
  9. * screen recording on Ubuntu
  10. hihocoder 1032 最长回文子串(Manacher)