hdoj3394 railway

题面

题目描述
有一个公园有n个景点,这n个景点由m条无向道路连接而成。
公园的管理员准备规划一一些形成回路的参观路线。如果一条道路被多条参观路线公用,那么这条路是冲突的;如果一条道路没在任何一个回路内,那么这条路是多余的道路。
问分别有多少条有冲突的路和多余的路

输入格式
包括多组数据 每组数据第一行2个整数n,m
接下来m行,每行2个整数x,y,表示从x到y有一条无向边。
输入数据以n=0,m=0结尾
输出格式
一行2个整数,表示你要求的多余的道路和冲突的道路的数量。

题解

这个很明显了,手推一下,第一问求割边的数量;第二问求有两个环以上的点双的点数之和。
第二问怎么找到满足题意的点双呢?如果一个点双点数=边数,那么就是一个满足题意的环。如果点数<边数,就说明不止一个环,就要计数了。

这里有个大问题——为何是点双而不是边双?

我手推了一组反例数据。
这里写图片描述
很明显,一整个都是一个边双连通图,除此之外,这个边双还内置了两个割点、三个点双。但是需要计算的只是最左边的四个点。
所以是点双。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int num=0;char c=' ';bool flag=true;
for(;c>'9'||c<'0';c=getchar())
if(c=='-')
flag=false;
for(;c>='0'&&c<='9';num=(num<<3)+(num<<1)+c-48,c=getchar());
return flag ? num : -num;
}
namespace graph{
const int maxn=10020;
const int maxm=100020;
struct node{
int y,next;
}a[maxm<<1];
int head[maxn],top=0;
void insert(int x,int y){
a[top].y=y;
a[top].next=head[x];
head[x]=top++;
}
int n,m;
void init(){
for(int i=1;i<=m;i++){
int x=read()+1;
int y=read()+1;
insert(x,y);
insert(y,x);
}
}
}using namespace graph;

namespace TARJAN{
int ans1,ans2;
int dfn[maxn],low[maxn],cnt,low1[maxn];
int block[maxn],dcc,size;
int sta[maxn],t=0;
vector<int>edcc;
void work(){//每一个点双都看一下
int co=0;
for(int x=0;x<size;x++)
for(int i=head[vdcc[x]];i+1;i=a[i].next)
if(block[a[i].y]==dcc)
co++;
co>>=1;
if(co>size)ans2+=co;
}
void tarjan(int x,int in_edge){
//tarjan计数割边和求点双
low[x]=dfn[x]=++cnt;
low1[x]=cnt;
sta[++t]=x;
for(int i=head[x];i+1;i=a[i].next){
int y=a[i].y;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
low1[x]=min(low1[x],low1[y]);
if(low1[y]>dfn[x])ans1++;
if(low[y]>=dfn[x]){
int u;
dcc++;size=0;
vdcc.clear();
do{
u=sta[t];
t--;
block[u]=dcc;
size++;

vdcc.push_back(u);

}while(u!=y);
block[x]=dcc;
vdcc.push_back(x);
size++;
work();
}
}
else {
low[x]=min(low[x],dfn[y]);
if(i!=(in_edge^1))
low1[x]=min(low1[x],dfn[y]);
}
}
}

}using namespace TARJAN;
void clean(){
memset(head,-1,sizeof head);
top=0;cnt=0;dcc=0;size=0;ans1=ans2=0;t=0;
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(block,0,sizeof block);
memset(sta,0,sizeof sta);
memset(low1,0,sizeof low1);
}

int main(){
//freopen("way.in","r",stdin);
//freopen("way.out","w",stdout);
n=read();m=read();
while(n||m){
clean();
init();
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,-1);
printf("%d %d\n",ans1,ans2);
n=read();m=read();
}
return 0;
}
文章目录
  1. 1. 题面
  2. 2. 题解
    1. 2.1. 这里有个大问题——为何是点双而不是边双?
    2. 2.2. code