洛谷 P3388 割点(割顶) 题解
2024-10-07 03:22:03
题面:
割点性质:
节点 u 如果是割点,当且仅当存在 u 的一个子树,子树中没有连向 u 的祖先的边(返祖边)。
换句话说,如果对于一个点u,它的子节点是v,如果low[v]>=dfn[u],就代表u的子图中没有返祖边,即该节点u是割点;
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct littlestar{
int to;
int nxt;
}star[];
int head[],cnt;
void add(int u,int v)
{
star[++cnt].to=v;
star[cnt].nxt=head[u];
head[u]=cnt;
}
int dfn[],low[];
int num;
int co[];
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(fa&&low[v]>=dfn[u]){
co[u]=; //注意,不可以在这里统计割点次数,因为有的点可能会多次进入该判断语句,比如说菊花图。
}
}
else if(v!=fa)
{
low[u]=min(low[u],dfn[v]);
}
} }
int main ()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++){
if(!dfn[i]) tarjan(i,);
}
int col=;
for(int i=;i<=n;i++){
if(co[i]){
++col;
}
}
cout<<col<<endl;
for(int i=;i<=n;i++){
if(co[i]){
cout<<i<<" ";
}
}
}
最新文章
- 佳佳的魔杖 (vijos 1283)
- JavaScript高级程序设计5.pdf
- Red Hat Enterprise Linux Server(RHEL) yum安装软件时This system is not registered with RHN. RHN support will be disabled. 的解决方法(转)
- 键盘enter事件时间页面绑定
- Putty是一个专业的SSH连接客户端
- 找回误删除的UBUNTU16.04桌面壁纸图片,或把桌面背景图片另存。20170114
- PgSql on Docker with HaProxy 反向代理
- python中的基础2
- vue 开发环境搭建
- Redis master/slave,sentinel,Cluster简单总结
- 乐观锁与悲观锁以及乐观锁的一种实现方式-CAS
- 第4月第20天 python re xls2lua
- 使用Flask-CKEditor集成富文本编辑框
- Linux可重入函数和线程安全的区别与联系(转)
- 基于Hexo+Node.js+github+coding搭建个人博客——基础篇
- 【转】如何选择Html.RenderPartial和Html.RenderAction
- zoj 1610 Count the Colors 线段树区间更新/暴力
- LeetCode: 58. Length of Last Word(Easy)
- Memcache集群安装与配置
- vue 基础核心学习
热门文章
- Editplus注册码生成代码
- Ubuntu下搜狗输入法乱码(二)
- MySQL数据库入门———常用基础命令
- Win10上安装Awvs 12原版程序和完美破解补丁详细步骤
- Class constructor FileManager cannot be invoked without &#39;new&#39; in undefined (line undefined, column undefined)
- 关于Spring3与Jdk8 遇到的问题ArrayIndexOutOfBoundsException:xxxxxx
- java中的基本数据类型简谈
- jpa repostiory
- TreeMap元素必须实现Comparable接口
- 微信小程序底部菜单栏的使用方法