题意:

给你一个无向图,你需要找出来其中有几个割点

割点/割项:
1、u不为搜索起点,low[v]>=dfn[u]
2、u为搜索起点,size[ch]>=2
3、一般情况下,不建议在tarjan中直接输出答案(可能会有重复)
4、在有重边的情况下,将tarjan传值中的father改为其编号,由于存边的连续性 
   只要判断 (当前编号)i != (father编号)pre^1

代码:

 1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 const int maxn=105;
8 int cnt,head[maxn],n,dfn[maxn],low[maxn],num,qua,root,iscut[maxn];
9 struct edge
10 {
11 int u,v,next;
12 }e[maxn*maxn];
13 void add_edge(int x,int y)
14 {
15 e[cnt].u=x;
16 e[cnt].v=y;
17 e[cnt].next=head[x];
18 head[x]=cnt++;
19 }
20 void tarjan(int x)
21 {
22 dfn[x]=low[x]=++num;
23 int flag=0;
24 for(int i=head[x];i!=-1;i=e[i].next)
25 {
26 int to=e[i].v;
27 if(!dfn[to])
28 {
29 tarjan(to);
30 low[x]=min(low[x],low[to]);
31 if(low[to]>=dfn[x])
32 {
33 flag++;
34 if(x!=root || flag>1) iscut[x]=1,qua++;
35 } //一个割点可能会多次经历iscut[x]=1,所以qua里面的值不是割点数目
36 }
37 else low[x]=min(dfn[to],low[x]);
38 }
39 }
40 int main()
41 {
42 while(~scanf("%d",&n) && n)
43 {
44 cnt=num=qua=0;
45 memset(iscut,0,sizeof(iscut));
46 memset(head,-1,sizeof(head));
47 memset(dfn,0,sizeof(dfn));
48 memset(low,0,sizeof(low));
49 int x,y;
50 char ch;
51 while(~scanf("%d",&x) && x)
52 {
53 while(~scanf("%d",&y))
54 {
55 scanf("%c",&ch);
56 add_edge(x,y);
57 add_edge(y,x);
58 if(ch=='\n'){
59 break;
60 }
61 }
62 }
63 // for(int i=0;i<cnt;++i)
64 // {
65 // printf("%d %d\n",e[i].u,e[i].v);
66 //
67 // }
68 for(int i=1;i<=n;++i)
69 {
70 if(!dfn[i])
71 {
72 //printf("**\n");
73 root=i;
74 tarjan(i);
75 }
76 }
77 int ans=0;
78 for(int i=1;i<=n;++i)
79 if(iscut[i]) ++ans;
80 printf("%d\n",ans);
81 }
82 return 0;
83 }

最新文章

  1. WCF自动添加消息头
  2. Python递归报错:RuntimeError: maximum recursion depth exceeded in comparison
  3. install LLVM
  4. Atom 备份神器 —— Sync Settings
  5. 设置SecureCRT配色和解决乱码问题
  6. Display: table-cell实现img、文字垂直居中
  7. discuz内置常用CSS代码分析
  8. viewmodel
  9. c++中new分配动态数组
  10. zoj 1842 Prime Distance
  11. JAVA之While语句、Do和For语句
  12. js学习--浏览器对象计时器setInterval()与setTimeout()的使用与区别
  13. JavaScript - 运算符 == 与 === 的区别
  14. ios获取权限
  15. DevExpress ASP.NET 使用经验谈(1)-XPO模型的创建
  16. Microsoft Message Analyzer (微软消息分析器,“网络抓包工具 - Network Monitor”的替代品)官方正式版现已发布
  17. Flow-Guided Feature Aggregation for Video Object Detection论文笔记
  18. ES6 对象的扩展(上)
  19. 关于python词典(Dictionary)的get()用法
  20. 新概念英语(1-67)The weekend

热门文章

  1. ThinkPHP5表单令牌刷新
  2. Openstack Nova 控制服务 和 计算服务 (六)
  3. 如何实现CentOS服务器的扩容??
  4. 【ORA】ORA-16629解决办法
  5. D2Admin 登录用户重新初始话右侧菜单
  6. python3.8.1安装cx_Freeze
  7. 二十五:XSS跨站值原理分类及攻击手法
  8. 日常分享:关于时间复杂度和空间复杂度的一些优化心得分享(C#)
  9. Git安装/VScode+Git+Github
  10. 盼望着,盼望着。它终于来了!!!剪辑Windows PC测试版!