判断割点的性质:

如果点y满足

low[y]>=dfn[x] 且不是根节点

或者是根节点,满足上述式子的有两个及其以上。

就是割点

如果是起点,那么至少需要两个子节点满足上述条件,因为它是根节点,那么必须有至少两个节点的以及其儿子节点的时间戳是比这个值小的,如图,否则根节点也只是

一个叶子节点。

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int SIZE = ;
int head[SIZE],ver[SIZE*],Next[SIZE*];
int dfn[SIZE],low[SIZE],stack[SIZE];
bool cut[SIZE];
int n,m,tot,num,root;
void add(int x,int y)
{
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
/*
编号
*/
int flag=;
for (int i=head[x]; i; i=Next[i])
{ /*
遍历
*/
int y=ver[i];
if (!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
if (low[y]>=dfn[x]) /*割点的性质*/
{
//就是找到一个点,这个点的时间戳是比期所有子节点的最小时间戳都要小于或者等于的
//那么我们只能通过这个点访问这个点
flag++;
if(x!=root || flag>)cut[x]=true;
//如果是根节点,那么它要是割点前提是它必须要有两个以上的子节点满足上述条件
}
}
else
{
low[x]=min(low[x],dfn[y]);
}
}
}
void init(){
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(Next,,sizeof(Next));
memset(ver,,sizeof(ver));
memset(head,,sizeof(head));
memset(stack,,sizeof(stack));
memset(cut,,sizeof(cut));
tot=;
num=;
}
int main()
{
char s[];
int a,b;
char ch;
while(scanf("%d",&n)&&n)
{
init();
while(scanf("%d",&a)&&a)
{
while(scanf("%d%c",&b,&ch))
{
add(a,b);
add(b,a);
if (ch=='\n')break;
}
}
int ans=;
for (int i=; i<=n; i++)
{
if (!dfn[i])root=i,tarjan(i);
}
ans=;
for (int i=; i<=n; i++)
{
if (cut[i])
{
ans++;
}
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. canvas初探1
  2. REST vs SOAP
  3. View(三)
  4. JVM总结
  5. vim 跳到指定行
  6. 前端学习笔记汇总(之merge方法)
  7. HDU 5754 Life Winner Bo (找规律and博弈)
  8. bmp to jpg
  9. 了解开源的许可证GPL、LGPL、BSD、Apache 2.0的区别 【转】
  10. Ubuntu14 或是其他系统当中关于sublimeSFTP超时解决方法
  11. JAVA面向对象-----构造方法
  12. MySQL一般查询日志或者慢查询日志历史数据的清理
  13. Centos6.8下SVN安装
  14. elasticsearch学习笔记——相关插件和使用场景
  15. Swift - 通过叠加UILabel来实现混合的进度条
  16. Three ways to make your WPF images pop out on MouseOver
  17. JS对象添加新的字段
  18. codeforces#516 Div2---ABCD
  19. [LeetCode 题解]: Generate Parentheses
  20. LeetCode OJ:Valid Parentheses(有效括号)

热门文章

  1. 2019.8.9 NOIP模拟测试15 反思总结
  2. JSP-Cookie和Session
  3. springMVC的功能和优点
  4. 系统日志和内核消息 $ dmesg$ less /var/log/messages$ less /var/log/secure$ less /var/log/auth
  5. Leetcode605.Can Place Flowers种花问题
  6. 七牛云+MPic-图床神器搭建
  7. python的工具pip进行安装时出现 No module named &#39;pip&#39;
  8. 基于 DataLakeAnalytics 的数据湖实践
  9. _STORAGE_WRITE_ERROR_:./Application/Runtime/Cache/Home/f8995a0e1afcdadc637612fae5a3b585.php
  10. Django-2.2.1版本关于无法使用makemigrations的错误