题目链接

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 ;
}

最新文章

  1. java并发编程(十七)内存操作总结
  2. 向内存0:200~0:23f依次传送数据0~3fh
  3. Jquery 之 使用选择器
  4. 解决访问StackOverFlow太慢的问题
  5. web快速开发c/s软件构架
  6. BitmapSource ConvertTo Bitmap
  7. ****Git 常用命令和使用思维导图
  8. 玩转EasyUi弹出框
  9. LED字符设备驱动实例及测试代码
  10. Contains Duplicate III —— LeetCode
  11. 排序算法——交换排序(冒泡排序、快速排序)(java)
  12. LR监控Windows Server 2008 R2系统资源提示“指定的网络名不可用。”
  13. YYHS-Floor it
  14. java读写锁ReadWriteLock
  15. 前端MVC Vue2学习总结(三)——模板语法、过滤器、计算属性、观察者、Class 与 Style 绑定
  16. [Apio2010] 巡逻
  17. Python中使用rrdtool结合Django进行带宽监控
  18. AOP之proceedingjoinpoint和joinpoint区别(获取各对象备忘)、动态代理机制及获取原理代理对象、获取Mybatis Mapper接口原始对象
  19. Oracle 12c client with .NET legacy Oracle driver
  20. Elastic Stack之搜索引擎基础

热门文章

  1. C# 1.0(2002)
  2. dp周训练 状态压缩
  3. 【PKUSC2019】线弦图【计数】【树形DP】【分治FFT】
  4. Linux开机启动和登录时各个文件的执行顺序
  5. 关于Spring3与Jdk8 遇到的问题ArrayIndexOutOfBoundsException:xxxxxx
  6. mybayis分页插件
  7. RF问题收集
  8. Python基本语法_运算符详解
  9. apache配置静态缓存
  10. Java Stream流排序null以及获取指定条数数据