洛谷 P3388 【模板】割点(割顶)(Tarjan)
2024-08-24 19:42:51
题目链接
https://www.luogu.org/problemnew/show/P3388
模板题
解题思路
怎样求割点?
- dfn :即时间戳,一张图的dfs序(dfs遍历时出现的顺序)
- 树边:连向孩子的边
- 反向边:连向祖先的边
- low :即一个点能到达的时间戳最小的边(反向边只能经过一条)
显然,一个点如果它的任意一个孩子的low大于等于这个点,那么这个点就是割点。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<stack>
using namespace std;
const int maxn=;
const int maxm=;
int n,m,cnt,dfn[maxn],low[maxn],times,p[maxn];
bool iscut[maxn];
struct edge{
int u;
int v;
int next;
}e[maxm];
stack<edge> S;
void insert(int u,int v){
++cnt;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].next=p[u];
p[u]=cnt;
}
void dfs(int u,int fa){
dfn[u]=low[u]=++times;
int child=;
for(int i=p[u];i!=-;i=e[i].next){
int v=e[i].v;
if(dfn[v]==){
child++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])iscut[u]=true;
}
else if(dfn[v]<dfn[u]&&v!=fa){
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-&&child==) iscut[u]=false;
}
int main()
{
cin>>n>>m;
memset(p,-,sizeof(p));
memset(low,0x3f3f3f,sizeof(low));
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
insert(x,y);
insert(y,x);
}
for(int i=;i<=n;i++){
if(!dfn[i]) dfs(i,-);
}
int ans=;
for(int i=;i<=n;i++){
if(iscut[i]) ans++;
}
cout<<ans<<endl;
for(int i=;i<=n;i++){
if(iscut[i]) cout<<i<<" ";
}
return ;
}
最新文章
- java并发编程(十七)内存操作总结
- 向内存0:200~0:23f依次传送数据0~3fh
- Jquery 之 使用选择器
- 解决访问StackOverFlow太慢的问题
- web快速开发c/s软件构架
- BitmapSource ConvertTo Bitmap
- ****Git 常用命令和使用思维导图
- 玩转EasyUi弹出框
- LED字符设备驱动实例及测试代码
- Contains Duplicate III —— LeetCode
- 排序算法——交换排序(冒泡排序、快速排序)(java)
- LR监控Windows Server 2008 R2系统资源提示“指定的网络名不可用。”
- YYHS-Floor it
- java读写锁ReadWriteLock
- 前端MVC Vue2学习总结(三)——模板语法、过滤器、计算属性、观察者、Class 与 Style 绑定
- [Apio2010] 巡逻
- Python中使用rrdtool结合Django进行带宽监控
- AOP之proceedingjoinpoint和joinpoint区别(获取各对象备忘)、动态代理机制及获取原理代理对象、获取Mybatis Mapper接口原始对象
- Oracle 12c client with .NET legacy Oracle driver
- Elastic Stack之搜索引擎基础