Network UVA - 315 无向图找割点
2024-10-16 02:29:55
题意:
给你一个无向图,你需要找出来其中有几个割点
割点/割项:
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 }
最新文章
- WCF自动添加消息头
- Python递归报错:RuntimeError: maximum recursion depth exceeded in comparison
- install LLVM
- Atom 备份神器 —— Sync Settings
- 设置SecureCRT配色和解决乱码问题
- Display: table-cell实现img、文字垂直居中
- discuz内置常用CSS代码分析
- viewmodel
- c++中new分配动态数组
- zoj 1842 Prime Distance
- JAVA之While语句、Do和For语句
- js学习--浏览器对象计时器setInterval()与setTimeout()的使用与区别
- JavaScript - 运算符 == 与 === 的区别
- ios获取权限
- DevExpress ASP.NET 使用经验谈(1)-XPO模型的创建
- Microsoft Message Analyzer (微软消息分析器,“网络抓包工具 - Network Monitor”的替代品)官方正式版现已发布
- Flow-Guided Feature Aggregation for Video Object Detection论文笔记
- ES6 对象的扩展(上)
- 关于python词典(Dictionary)的get()用法
- 新概念英语(1-67)The weekend