这个题目描述好难理解呀qwq...

传送门

分析

在读懂题之后我们不难发现这道题实际就是在求一张图中有多少个割点。只需要注意读入方式即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int n,dfn[],low[],cnt,sum,ans,is[];
vector<int>v[];
inline void init(){
for(int i=;i<=;i++)v[i].clear();
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(is,,sizeof(is));
cnt=sum=ans=;
}
inline void tarjan(int x,int fa){
int son=;
dfn[x]=low[x]=++cnt;
for(int i=;i<v[x].size();i++)
if(v[x][i]!=fa){
if(!dfn[v[x][i]]){
son++;
tarjan(v[x][i],x);
low[x]=min(low[x],low[v[x][i]]);
if(dfn[x]<=low[v[x][i]])is[x]=;
}else low[x]=min(low[x],dfn[v[x][i]]);
}
if(!fa&&son==)is[x]=;
}
int main(){
int i,j,k;
scanf("%d",&n);
while(n){
init();
int x,y;
scanf("%d",&x);
while(x){
while(getchar()!='\n'){
scanf("%d",&y);
v[x].push_back(y);
v[y].push_back(x);
}
scanf("%d",&x);
}
for(i=;i<=n;i++)
if(!dfn[i])tarjan(i,);
for(i=;i<=n;i++)
if(is[i])ans++;
printf("%d\n",ans);
scanf("%d",&n);
}
return ;
}

最新文章

  1. $(this)在ajax中无效的解决方案
  2. Git命令使用总结
  3. 网络初见&amp;网络监测
  4. IOS开发之多线程 -- GCD的方方面面
  5. 【Linux】Linux 目录结构
  6. BendFord&#39;s law&#39;s Chi square test
  7. Mongodb 主从复制与副本集实验
  8. [daily][archlinux][pacman] local database 损坏
  9. 自动化运维——一键安装MySQL
  10. bzoj2209 2329
  11. 用Python实现常见排序算法
  12. Sqlserver系列(二) 模糊查询 like
  13. 让UltraEdit成为java编译器
  14. 第三周LINUX学习笔记
  15. javaweb聊天室源码免费
  16. TJU ACM-ICPC Online Judge—1191 The Worm Turns
  17. springBoot总结
  18. koa源码之delegate使用
  19. 二、Java多人博客系统-演变
  20. Spring MVC静态资源处理(转)

热门文章

  1. cocos2d-html5 中的性能优化
  2. UVALive 3635 Pie(二分法)
  3. 3.Monkey Script小案例
  4. JDBC小常识
  5. CentOS6.5上安装Python2.7和PIP
  6. [转载]Linux 内核list_head 学习(一)
  7. 机器学习:数据归一化(Scaler)
  8. Python内置:items()方法
  9. AngularJS:SQL
  10. 转:Oracle下创建ASM磁盘总结