当前位置: 首页 > news >正文

【CF19E】Fairy - Harvey

题意

给定一个无向图,问删掉那条边使得给图可以变成一个二分图。

思路

回顾二分图的定义:不存在奇环的图。
由于不保证连通图,所以可以把整个图分成若干个连通块来考虑。

  1. 若所有连通块都是二分图:则此时删掉哪一条边剩下的都能形成二分图,答案是 \(m\).
  2. 若存在两个及以上的连通块是二分图:则此时不合法,删掉那一条边都一定会有二分图。

限制掉前两种后,接下来考虑只有一个连通块是二分图,于是可以转化为一个连通图的问题。
若删去一条边使得删完后不存在奇环,则删去的边一定满足以下条件:

  1. 在所有奇环中。
    如果删去的边不在其中一个奇环里面,则连通图一定还存在一个奇环,此时不可能为二分图。
  2. 不在任意一个偶环中。
    考虑要删的一条边,一定满足以下性质:
    First.一定连通两个连通块。
    Second.一定有一条另外的边联通两个连通块,形成一个奇环。
    考虑到如果删去这条边的效果是可以给其中一个连通块的点都变色,才能使得染色不矛盾。
    而此时若存在一个偶环,则变完色后偶环的点又会有矛盾了,即证。

然后接下来就是怎么来写了。
可以把连通图以 \(DFS\) 树的方式显现,则每一个环都存在一条返祖边,然后就可以用树上差分做了。

code

#include<bits/stdc++.h>
#define ll long longusing namespace std;const int N = 1e4+5;struct Edge{int to,nxt,id;
}e[N<<1];int tot=0,cnt=0,res=0;
int head[N],dep[N],s[N],fa[N],p;
bool flag=0;
bool vis[N];
vector<ll> vec;void add_Edge(int u,int v,int id){e[tot].to=v,e[tot].nxt=head[u],e[tot].id=id;head[u]=tot++;
}void dfs(int u,int f){dep[u]=dep[f]+1;fa[u]=f;vis[u]=1;for(int i=head[u];~i;i=e[i].nxt) {int v=e[i].to;if(v==f)continue;if(vis[v]){if(dep[v]<dep[u]){ll siz=dep[u]-dep[v]+1;if(siz&1)s[u]++,s[v]--,res++,flag=1,p=e[i].id;else s[u]--,s[v]++;}}else dfs(v,u);}
}void DFS(int u){vis[u]=1;for(int i=head[u];~i;i=e[i].nxt){int v=e[i].to,idx=e[i].id;if(vis[v])continue;DFS(v);s[u]+=s[v];if(s[v]==res)vec.push_back(idx);}
}
int n,m;
int main() {memset(head,-1,sizeof(head));cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add_Edge(u,v,i);add_Edge(v,u,i);}for(int i=1;i<=n;i++){flag=0;if(!vis[i])dfs(i,0);if(flag){cnt++;if(cnt>1){cout<<-1;return 0;}memset(vis,0,sizeof(vis));DFS(i);}}if(cnt){if(res==1)vec.push_back(p);cout<<vec.size()<<"\n";sort(vec.begin(),vec.end());for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";}else {cout<<m<<"\n";for(int i=1;i<=m;i++)cout<<i<<" ";}return 0;
}
http://www.hskmm.com/?act=detail&tid=21001

相关文章:

  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践
  • 软件工程中线性回归应用
  • 解决秒杀高并发的一些方案
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网
  • 9.29模拟赛总结
  • 多corner综合
  • 优化 if/else 的四种设计模式
  • Day11-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\oop\demo06
  • 牛客周赛 Round 111
  • OpenLayers地图交互 -- 章节十一:拖拽材料交互详解
  • 2025年人工智能与智能装备国际学术会议(AIIE 2025)
  • 通过IDOR实现权限提升导致未授权用户注入
  • APUE学习笔记之基础知识(一) - Invinc
  • Syslog日志集成搭建
  • 定义工业生产新范式!网易灵动发布全球首款全域智能无人装载机“灵载”
  • 国有银行人力资源数字化转型的合规突围与效能跃迁
  • Java 类类型
  • OpenFeign 继承FeignClient客户端注意事项
  • 9月29日
  • JVM调优实战及常量池详解
  • Cisco Identity Services Engine (ISE) 3.5 - 基于身份的网络访问控制和策略实施系统
  • 03-控制台项目创建与结构说明
  • 赋能智慧应急:国标GB28181平台EasyGBS视频技术如何成为气象灾害预警新工具
  • NET各个版本新增的特性和语法糖
  • xinference推理embedding等小模型
  • day15-项目上线
  • opencv学习记录6
  • 努力的轨迹,通往成长的旅程——赵欣彤的自我介绍
  • 第2章 day02 requests基础