[kuangbin带你飞]专题九 连通图B - Network UVA - 315
2024-09-03 15:33:59
判断割点的性质:
如果点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 ;
}
最新文章
- canvas初探1
- REST vs SOAP
- View(三)
- JVM总结
- vim 跳到指定行
- 前端学习笔记汇总(之merge方法)
- HDU 5754 Life Winner Bo (找规律and博弈)
- bmp to jpg
- 了解开源的许可证GPL、LGPL、BSD、Apache 2.0的区别 【转】
- Ubuntu14 或是其他系统当中关于sublimeSFTP超时解决方法
- JAVA面向对象-----构造方法
- MySQL一般查询日志或者慢查询日志历史数据的清理
- Centos6.8下SVN安装
- elasticsearch学习笔记——相关插件和使用场景
- Swift - 通过叠加UILabel来实现混合的进度条
- Three ways to make your WPF images pop out on MouseOver
- JS对象添加新的字段
- codeforces#516 Div2---ABCD
- [LeetCode 题解]: Generate Parentheses
- LeetCode OJ:Valid Parentheses(有效括号)
热门文章
- 2019.8.9 NOIP模拟测试15 反思总结
- JSP-Cookie和Session
- springMVC的功能和优点
- 系统日志和内核消息 $ dmesg$ less /var/log/messages$ less /var/log/secure$ less /var/log/auth
- Leetcode605.Can Place Flowers种花问题
- 七牛云+MPic-图床神器搭建
- python的工具pip进行安装时出现 No module named &#39;pip&#39;
- 基于 DataLakeAnalytics 的数据湖实践
- _STORAGE_WRITE_ERROR_:./Application/Runtime/Cache/Home/f8995a0e1afcdadc637612fae5a3b585.php
- Django-2.2.1版本关于无法使用makemigrations的错误