现在打算重新学习图论的一些基础算法,包括像桥,割顶,双连通分量,强连通分量这些基础算法我都打算重敲一次,因为这些量都是可以用tarjan的算法求得的,这次的割顶算是对tarjan的那一类算法的理解的再次实现吧,后面打算做一下桥的判断和边双连通的关系,边双连通处理的时候如果又重边的话会很不一样,割顶也会相应的不一样,这里的代码是没有考虑重边的,后面再写一个考虑重边的吧。
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
|
#pragma warning(disable:4996) #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cstdio> #include<vector> #include<cmath> #define maxn 150 using
namespace std;
vector< int > G[maxn];
int
n;
int
low[maxn], pre[maxn];
int
dfs_clock;
bool
iscut[maxn];
int
dfs( int
u, int
fa)
{ int
lowu = pre[u] = ++dfs_clock; int
ch = 0;
for
( int i = 0; i < G[u].size(); i++){
int
v = G[u][i];
if
(!pre[v]){
ch++;
int
lowv=dfs(v, u);
lowu = min(lowu, lowv);
if
(lowv >= pre[u]){
iscut[u] = true ;
//if (lowv>pre[u]) (u,v)是桥
}
}
else
if (pre[v] < pre[u] && v != fa){
lowu = min(lowu, pre[v]);
}
}
if
(fa < 0 && ch == 1) iscut[u] = false ;
return
low[u] = lowu;
} void
init()
{ memset (low, 0, sizeof (low));
memset (pre, 0, sizeof (pre));
memset (iscut, 0, sizeof (iscut));
dfs_clock = 0;
for
( int i = 1; i <= n; i++){
if
(!pre[i]) dfs(i, -1);
}
} int
main()
{ while
(cin >> n&&n)
{
for
( int i = 0; i <= n; i++) G[i].clear();
int
a,b; char
c;
while
( scanf ( "%d" , &a)==1&&a){
while
((c = getchar ()) != ‘\n‘ ){
scanf ( "%d" , &b);
G[a].push_back(b);
G[b].push_back(a);
}
}
init(); int
ans = 0;
for
( int i = 1; i <= n; i++){
if
(iscut[i]) ans++;
}
printf ( "%d\n" , ans);
}
return
0;
} |