#include<bits/stdc++.h>
using namespace std;
typedef long long ll; int n,m;
const int maxn=1e5+;
const int maxm=maxn<<;
struct node
{
int to;
int nxt;
}e[maxm];
int head[maxn];
int tot;
int id;
int root;
int low[maxn];
int num[maxn];
bool vis[maxn];
int pa[maxn];
int cnt=;
int art[maxn];
void init()
{
memset(head,-,sizeof(head));
tot=;
id=;
memset(low,-,sizeof(low));
memset(num,-,sizeof(num));
memset(vis,false,sizeof(vis));
memset(pa,-,sizeof(pa));
cnt=;
memset(art,,sizeof(art));
}
void add(int u,int v)
{
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot++;
}
void findArt(int u)
{
vis[u]=true;
low[u]=num[u]=++id;
for(int i=head[u];i!=-;i=e[i].nxt)
{
int v=e[i].to;
//树边
if(!vis[v])
{
pa[v]=u;
findArt(v);
if(low[v]>=num[u]&&u!=root)
{
art[cnt++]=u;
}
low[u]=min(low[u],low[v]);
}
else if(pa[v]!=u) //回退边
{
low[u]=min(low[u],num[v]);
}
}
} void printArt()
{
int tmp=;
for(int i=head[root];i!=-;i=e[i].nxt)
{
if(pa[e[i].to]==root) tmp++;
}
if(tmp>=) art[cnt++]=root;
for(int i=;i<cnt;i++)
{
printf("%d ",art[i]);
}
puts("");
} int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
int u,v;
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
root=;
findArt(root);
printArt();
}
return ;
}

Tarkjan求无向图割点

http://www.cnblogs.com/llhthinker/p/4954082.html

最新文章

  1. 解析Java类和对象的初始化过程
  2. ios 跟踪UITextField更改的简单方法
  3. Android设计画面中有EditText时取消启动时自动获得焦点调用系统输入法的方法
  4. LCA(RMQ)
  5. 已有数据表的Mysql字符编码修改
  6. 【滚动数组】 dp poj 1036
  7. 基于SSE实现的极速的矩形核腐蚀和膨胀(最大值和最小值)算法。
  8. org.hibernate.validator.constraints.NotBlank&#39; validating type &#39;java.lang.Integer
  9. MySQL巧建sum索引帮我们提高至少100%的效率
  10. Oracle课程档案,第八天
  11. CNN卷积核计算
  12. Linux下批量修改文件名(rename)
  13. linux df查看硬盘使用量 du查看文件所占大小
  14. hdu 1.3.2 Moving Tables
  15. android手机如何获取手机号
  16. poj2506 Tiling
  17. Python概念-迭代器的__iter__和__next__
  18. RabbitMq初探——消息确认
  19. 技术串讲 CAS 有用
  20. 解决h5底部输入框在ios被软键盘顶飞 软键盘消失还下不来

热门文章

  1. Longest Increasing Subsequence的两种算法
  2. jmeter中通过beanshell访问eclipse中导出jar中的java类的方法
  3. vue分环境打包配置方法一
  4. 第1节 flume:11、flume的failover机制实现高可用
  5. xheditor的实例程序—类似word的编辑器
  6. mysql 复制中的 paxso 的两阶段和事务两阶段的区别
  7. javascript(函数式编程思考) ---&gt; Map-Filter-quicksort-Collatz序列-Flodl-Flodr
  8. 对于WebAssembly编译出来的.wasm文件js如何调用
  9. 51nod——1174 区间中最大的数(ST)
  10. 洛谷 P1483 序列变换