题目大意:有向图求割点

题目思路:

一个点u为割点时当且仅当满足两个两个条件之一:

1.该点为根节点且至少有两个子节点

2.u不为树根,且满足存在(u,v)为树枝边(或称 父子边,即u为v在搜索树中的父亲),使得 dfn(u)<=low(v)。

然后注意读入,很容易RE

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXSIZE 1005
#define LL long long using namespace std; int vis[MAXSIZE],Map[MAXSIZE][MAXSIZE],low[MAXSIZE],dfn[MAXSIZE],pre[MAXSIZE],Time,n,ans,son; void Tarjan(int u,int fa)
{
pre[u]=fa;
low[u]=dfn[u]=++Time;
for(int i=; i<=n; i++)
{
if(!Map[u][i] || u==i) continue;
if(!dfn[i])
{
Tarjan(i,u);
low[u]=min(low[u],low[i]);
}
else if(fa!=i)
{
low[u]=min(low[u],dfn[i]);
}
}
} void Init()
{
memset(Map,,sizeof(Map));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(vis,,sizeof(vis));
memset(pre,,sizeof(pre));
Time=;
ans=;
son=;
} int main()
{
int a,b;
char ch,op;
while(scanf("%d",&n),n)
{
Init();
getchar();
while(scanf("%d",&a),a)
{
while(scanf("%d%c",&b,&op))
{
Map[a][b]=Map[b][a]=;
if(op=='\n') break;
}
}
Tarjan(,);
for(int i=;i<=n;i++)
{
if(pre[i]==)
son++;
else if(dfn[pre[i]] <= low[i])
vis[pre[i]]=;
}
if(son > ) ans++;
for(int i=;i<=n;i++)
if(vis[i]) ans++;
printf("%d\n",ans);
}
return ;
}

最新文章

  1. mysql myisam简单分表设计
  2. 2016年12月27日 星期二 --出埃及记 Exodus 21:22
  3. Chromium的UI绘制初探
  4. OpenJudge/Poj 1658 Eva&#39;s Problem
  5. IIS搭建的http文件服务器
  6. 二维码类库--phpqrcode使用简介
  7. testNG实现test失败后重复执行,
  8. 0基础搭建Hadoop大数据处理-环境
  9. annotation-config, annotation-driven, compont-scan 区别
  10. 首次在C#程序中用log4net
  11. python字符串常用的方法解析
  12. JDBC 基础
  13. Noip2017 普及 T3 Chess
  14. linux下find和grep命令详解
  15. nodejs的express框架(request,response方法汇总)
  16. ambari HDFS-HA 回滚
  17. http中的Content-Type
  18. Java中的网络编程-3
  19. APPIUM-----自动发现兼容的Chromedrivers
  20. nyoj 题目21 三个水杯

热门文章

  1. Failed to resolve: com.android.support:appcompat-v7:28 问题解决
  2. mysql中CONCAT值为空的问题解决办法
  3. nginx location反向代理不对等时的处理
  4. 绑定本地的Session
  5. 三层结构、MVC的简介
  6. GDB调试qemu-kvm
  7. 1053. Path of Equal Weight (30)
  8. sklearn—特征工程
  9. Hbase学习01
  10. js和jQuery中的事件绑定与普通事件