题面

    割点性质:
    节点 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<<" ";
}
}
}
 

最新文章

  1. 佳佳的魔杖 (vijos 1283)
  2. JavaScript高级程序设计5.pdf
  3. Red Hat Enterprise Linux Server(RHEL) yum安装软件时This system is not registered with RHN. RHN support will be disabled. 的解决方法(转)
  4. 键盘enter事件时间页面绑定
  5. Putty是一个专业的SSH连接客户端
  6. 找回误删除的UBUNTU16.04桌面壁纸图片,或把桌面背景图片另存。20170114
  7. PgSql on Docker with HaProxy 反向代理
  8. python中的基础2
  9. vue 开发环境搭建
  10. Redis master/slave,sentinel,Cluster简单总结
  11. 乐观锁与悲观锁以及乐观锁的一种实现方式-CAS
  12. 第4月第20天 python re xls2lua
  13. 使用Flask-CKEditor集成富文本编辑框
  14. Linux可重入函数和线程安全的区别与联系(转)
  15. 基于Hexo+Node.js+github+coding搭建个人博客——基础篇
  16. 【转】如何选择Html.RenderPartial和Html.RenderAction
  17. zoj 1610 Count the Colors 线段树区间更新/暴力
  18. LeetCode: 58. Length of Last Word(Easy)
  19. Memcache集群安装与配置
  20. vue 基础核心学习

热门文章

  1. Editplus注册码生成代码
  2. Ubuntu下搜狗输入法乱码(二)
  3. MySQL数据库入门———常用基础命令
  4. Win10上安装Awvs 12原版程序和完美破解补丁详细步骤
  5. Class constructor FileManager cannot be invoked without &#39;new&#39; in undefined (line undefined, column undefined)
  6. 关于Spring3与Jdk8 遇到的问题ArrayIndexOutOfBoundsException:xxxxxx
  7. java中的基本数据类型简谈
  8. jpa repostiory
  9. TreeMap元素必须实现Comparable接口
  10. 微信小程序底部菜单栏的使用方法