小结:双连通分量 & 强连通分量 & 割点 & 割边
2024-08-26 07:38:46
概要:
各种dfs时间戳。。全是tarjan(或加上他的小伙伴)无限膜拜tarjan orzzzzzzzzz
技巧及注意:
强连通分量是有向图,双连通分量是无向图。
强连通分量找环时的决策和双连通的决策十分相似,但不完全相同。
强连通分量在if(FF[v])后边的else if还要特判是否在栈里,即vis[v],然后才更新LL[u]
割点和双连通分量因为是无向图所以要判个fa,可以在dfs时维护个fa参数
割点如果要求分割的分量,那么就是这个节点对他的子树是割点的数目+1。
割点不需要栈维护但是要在后边判当前节点是否为root(即child==1且为root时,这个点就不是割点),而双连通分量不需要特判根节点,而需要在LL[v]>=FF[u]那里直接维护bcc即可。
割边的话其实就是割边的特例即可,即LL[u]>FF[u]就行了。。千万不要写错。。
边-双连通分量的话比点的好做,就是求出割边后所有不经过割边的环就都是了,dfs之。
点-双连通分量似乎也是存边然后取边集中的点?等做完bzoj cactus先吧。。。
缩点后一定要注意重边啊!!!
割点例题:
- 【POJ】1523 SPF(割点)(注意特判root)
割边例题:
- 【vijos】1769 网络的关键边(割边)(注意割边不要写错)
双连通分量例题:
- 【POJ】2942 Knights of the Round Table(双连通分量)(注意不要忘记栈是在两个if内添加的)
将有环图转换成dag然后解决问题,例题:
最新文章
- JVM内存管理------GC算法精解(五分钟教你终极算法---分代搜集算法)
- viewport和media query
- nohup之no hang up, kill, ps -ef, ps aux, grep
- 3D模型修改
- [转]Linux中find常见用法示例
- xshell十大技巧
- document.getElementsByClassName在ie8及其以下浏览器的兼容性问题
- jforum(1)--环境搭建
- 7. Buffer_包描述文件_npm常用指令_fs文件读写_模块化require的规则
- linux CentOS 安装 nginx
- Spring Cloud 之Eureka(一)
- 你真的理解了for循环吗?反正我是没有
- FFMPEG增加和提取字幕流
- WebService学习概念总结
- openhtmltopdf 支持自定义字体、粗体
- python 发送邮件脚本
- video组件的使用
- 暂时关闭 windows 病毒防护
- 项目 - RM 部署上centos7 之后出现的一些问题和解决方法
- King's Quest POJ - 1904(强连通分量)
热门文章
- Cg入门21:Fragment shader - 2D纹理採样
- Java设计模式(二)-单例模式
- 03-maven学习-eclipse中创建maven项目
- java基础学习总结——GUI编程(二) 未学习
- phpcms 留言板
- 你所不知道的 CSS 阴影技巧与细节 滚动视差?CSS 不在话下 神奇的选择器 :focus-within 当角色转换为面试官之后 NPOI 教程 - 3.2 打印相关设置 前端XSS相关整理 委托入门案例
- quartusii开发过程中路径不能出现空格或中文
- GraphicsMagick 学习笔记
- 使用SOCKET实现TCP/IP协议的通讯
- CentOS安装使用git