题目链接

题意:求所给无向图中一共有多少个割顶

用的lrj训练指南P314的模板

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; const int N=;
struct Edge
{
int to,next;
Edge(){}
Edge(int _to,int _next)
{
to=_to;
next=_next;
}
}edge[N*N*];
int head[N]; int dfn[N],low[N];
int iscut[N];
int n,tot;
int time_tag; void addedge(int u,int v)
{
edge[tot]=Edge(v,head[u]);
head[u]=tot++;
} void init()
{
memset(dfn,,sizeof(dfn));
memset(iscut,,sizeof(iscut));
memset(head,-,sizeof(head));
tot=time_tag=;
} void dfs(int u,int pre)
{
low[u]=dfn[u]=++time_tag;
int child=; //子节点数目
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(!dfn[v]) // 把dfn[]当vis[]使用
{
child++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
iscut[u]=;
}
else if(dfn[v]<dfn[u] && v!=pre)
low[u]=min(low[u],dfn[v]);
}
if(pre<&&child==) iscut[u]=; //只有一个孩子的根节点
} int main()
{
while(scanf("%d",&n)>&&n)
{
init();
int u,v;
while(scanf("%d",&u)>&&u)
{
while(getchar()!='\n')
{
scanf("%d",&v);
addedge(u,v);
addedge(v,u);
}
}
dfs(,-);
int ans=;
for(int i=;i<=n;i++)
if(iscut[i]) ans++;
printf("%d\n",ans);
}
}

最新文章

  1. 迭代器模式/iterator模式/对象行为型模式
  2. 【Win10 应用开发】从前台应用触发后台任务
  3. SQLServer控制用户访问权限表
  4. 国际化(i18n)
  5. 续Gulp使用入门编译Sass
  6. 如何在ZBrush中添加毛发
  7. 批量硬关联本地AD帐号与Office云端帐号
  8. java 时间戳与日期字符串相互转换
  9. XML Schema (2)
  10. CSS的权重(转)
  11. jxl创Excel档java示例代码说明
  12. leetcode[68] Climbing Stairs
  13. Centos下关于ssh、scp与rsync设置与应用
  14. 微信小程序源码推荐
  15. 一起来Fit TDMA over WiFi(3)
  16. CSS后代选择器“空格”和“&gt;”的使用辨析
  17. HTML学习感悟
  18. mysql+mycat实现读写分离
  19. MAC OS X&amp;Vmware
  20. Js中带有小数的值相加产生的问题

热门文章

  1. linux查看硬盘信息
  2. HttpClient设置忽略SSL,实现HTTPS访问, 解决Certificates does not conform to algorithm constraints
  3. python中的各个模块
  4. zimg 服务器配置文件
  5. 用seaborn对数据可视化
  6. index.html(xpath素材)
  7. go net库
  8. pg_receivewal实践
  9. JS跨域--window.name
  10. [2019上海网络赛J题]Stone game