博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 1144 Network (割点)
阅读量:4984 次
发布时间:2019-06-12

本文共 1404 字,大约阅读时间需要 4 分钟。

#include
#include
#include
using namespace std;const int N=110;int num[N],low[N],head[N],vis[N];bool cut[N];int k,n,cnt,root;struct Edge{ int to,next;}edge[N<<1];void addedge(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++;}void Tarjan(int u,int fa){ int son=0; vis[u]=1; num[u]=low[u]=++k; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(vis[v]==1 && v!=fa) low[u]=min(low[u],num[v]); if(vis[v]==0){ Tarjan(v,u); son++; low[u]=min(low[u],low[v]); if((u==root && son>1) || (u!=root && num[u]<=low[v])) cut[u]=1; } } vis[u]=2;}int main(){ while(~scanf("%d",&n)&&n){ memset(head,-1,sizeof(head)); memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis)); memset(cut,0,sizeof(cut)); cnt=0; int u,v; while(scanf("%d",&u) && u){ while(getchar()!='\n'){ scanf("%d",&v); addedge(u,v); addedge(v,u); } } root=1; Tarjan(root,-1); int ans=0; for(int i=1;i<=n;i++) if(cut[i]) ans++; printf("%d\n",ans); } return 0;}

 

转载于:https://www.cnblogs.com/lalalatianlalu/p/9110293.html

你可能感兴趣的文章
DNS用的是TCP协议还是UDP协议
查看>>
JDK8集合类源码解析 - HashSet
查看>>
[面试没有回答上的问题4]常用字符串和数组的操作。
查看>>
WPF知识点全攻略09- 附加属性
查看>>
敏捷开发 流程 - 及产出
查看>>
关于SQL Server 2017中使用json传参时解析遇到的多层解析问题
查看>>
[转]SVN客户端解决authorization failed问题
查看>>
/etc/init.d目录和/etc/rc.local脚本
查看>>
Kubernetes StatefulSets
查看>>
用Python对html进行编码
查看>>
[转载]Java文件路径详解
查看>>
18.3.2从Class上获取信息(构造器)
查看>>
【TortoiseGit】TortoiseGit将本地库push到远端
查看>>
怎么样学习算法导论理论知识-算法何用
查看>>
Jenkins使用手册及总结
查看>>
Latest Common Ancestor
查看>>
getByClass--获取指定标签且class为指定的所有元素
查看>>
三点顺序
查看>>
拟物化设计与扁平化设计
查看>>
PS小实验-去除水印
查看>>