P3388 【模板】割点(割顶)

题目背景

割点

题目描述

给出一个n个点,m条边的无向图,求图的割点。

输入输出格式

输入格式:

第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

输出格式:

第一行输出割点个数

第二行按照节点编号从小到大输出节点,用空格隔开

输入输出样例

输入样例#1: 复制

6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
输出样例#1: 复制

1
5

说明

n,m均为100000

tarjan 图不一定联通!!!

分析

tarjan求割点

code

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib> using namespace std; const int N = ;
struct Edge{
int to,nxt;
}e[N<<];
int head[N],dfn[N],low[N];
bool iscut[N];
int tn,tot; inline char nc() {
static char buf[],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2) ? EOF : *p1++;
}
inline int read() {
int x = ,f = ;char ch = nc();
for (; ch<''||ch>''; ch = nc())
if (ch=='-') f = -;
for (; ch>=''&&ch<=''; ch = nc())
x = x*+ch-'';
return x * f;
} void add_edge(int u,int v) {
e[++tot].to = v,e[tot].nxt = head[u],head[u] = tot;
} void tarjan(int u,int fa) {
low[u] = dfn[u] = ++tn;
int cnt_son = ;
for (int i=head[u]; i; i=e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) {
cnt_son++;
tarjan(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< && cnt_son==) iscut[u] = false;
}
int main() {
int n = read(),m = read();
for (int u,v,i=; i<=m; ++i) {
u = read(),v = read();
add_edge(u,v),add_edge(v,u);
}
for (int i=; i<=n; ++i)
if (!dfn[i]) tarjan(i,-); int ans = ;
for (int i=; i<=n; ++i)
if (iscut[i]) ans++;
printf("%d\n",ans);
for (int i=; i<=n; ++i)
if (iscut[i]) printf("%d ",i);
return ;
}

最新文章

  1. mybatis批量删除提示类型错误
  2. jstl fortokens 分割字符串
  3. thinkphp的学习笔记
  4. LESS介绍及其与Sass的差异
  5. Python基础篇【第2篇】: Python自定义函数
  6. thinkphp 实现无限极分类
  7. Android 基础(设备显示密度/图片自适应
  8. Java ServletContext 详解
  9. mac下使用brew安装svn javahl的问题
  10. mac os apache 配置方法详细介绍
  11. 在code first结构下的生成的数据迁移文件,upadate-database失败
  12. hibernate-Maven
  13. Vector的浅析
  14. angularJs $mdDialog和$uibModal弹框关闭传值
  15. java自动化-数据驱动junit演示,下篇
  16. __x__(32)0908第五天__Photoshop的基本操作
  17. linux下用命令安装node&amp;pm2
  18. QML-WebEngineView加载html(Echarts绘图)
  19. 传入mybatis的xml为Long型时报There is no getter for property named &#39;VARCHAR&#39; in
  20. 在eclipse中,使用spring tool suite配置spring环境

热门文章

  1. Java设计模式之单例设计模式总结
  2. Java @Validated 遇到的大坑
  3. C#字符串变量使用
  4. storm中的topology-worker-executor-task
  5. dao层写展示自己需要注意的问题
  6. bootstrap fileinput 上传文件
  7. OPEN SQL
  8. angularJS在移动端的点击事件延迟问题
  9. Linux系统日志分析
  10. Game Engine Architecture