1
/*
2
双拓扑排序：抄的，以后来补
3
详细解释：
http://blog.csdn.net/u012774187/article/details/40736995
4
*/
5
#include <cstdio>
6
#include <algorithm>
7
#include <iostream>
8
#include <sstream>
9
#include <cstring>
10
#include <cmath>
11
#include <
string
>
12
#include <vector>
13
#include <queue>
14
#include <map>
15
#include <
set
>
16
#include <ctime>
17
#include <cstdlib>
18
using
namespace
std;
19
20
#define
lson l, mid, rt << 1
21
#define
rson mid + 1, r, rt << 1 | 1
22
typedef
long
long
ll;
23
24
const
int
MAXN = 1e3 +
10
;
25
const
int
INF =
0x3f3f3f3f
;
26
const
double
PI = acos (-
1.0
);
27
const
double
EPS = 1e-
9
;
28
struct
Edge
29
{
30
int
v, nxt;
31
}e[MAXN *
MAXN];
32
int
in
[MAXN],
out
[MAXN];
33
int
re[MAXN], head[MAXN];
34
bool
vis[MAXN];
35
map<
string
,
int
>
M;
36
vector<
int
>
G[MAXN];
37
int
ecnt, cnt;
38
39
int
TopoSort(
void
)
40
{
41
queue<
int
> Q1, Q2;
//
Q1 !re Q2 re
42
for
(
int
i=
1
; i<=cnt; ++
i)
43
{
44
if
(!
in
[i])
45
{
46
if
(!
re[i]) Q1.push (i);
47
else
Q2.push (i);
48
}
49
}
50
51
int
ans =
0
;
52
while
(!Q1.empty () || !
Q2.empty ())
53
{
54
if
(Q1.empty () && !Q2.empty ())
//
重启
55
{
56
ans++
;
57
while
(!Q2.empty ())
//
所有都重启安装
58
{
59
Q1.push (Q2.front ()); Q2.pop ();
60
}
61
}
62
while
(!
Q1.empty ())
63
{
64
int
u =
Q1.front (); Q1.pop ();
65
vis[u] =
true
;
66
for
(
int
i=head[u]; i!=-
1
; i=
e[i].nxt)
67
{
68
int
v =
e[i].v;
69
if
(!(--
in
[v]))
70
{
71
if
(!
re[v]) Q1.push (v);
72
else
Q2.push (v);
73
}
74
}
75
}
76
}
77
78
return
ans;
79
}
80
81
void
init(
void
)
82
{
83
M.clear ();
84
ecnt = cnt =
0
;
85
memset (
in
,
0
,
sizeof
(
in
));
86
memset (
out
,
0
,
sizeof
(
out
));
87
memset (re,
0
,
sizeof
(re));
88
memset (head, -
1
,
sizeof
(head));
89
memset (vis,
false
,
sizeof
(vis));
90
}
91
92
void
add_edge(
int
u,
int
v)
93
{
94
e[ecnt].nxt =
head[u];
95
e[ecnt].v =
v;
96
head[u] = ecnt++
;
97
}
98
99
int
main(
void
)
//
HDOJ 5098 Smart Software Installer
100
{
101
//
freopen ("I.in", "r", stdin);
102
103
string
s;
104
char
name[
1050
];
105
int
n, cas =
0
; scanf (
"
%d
"
, &
n); getchar (); getchar ();
106
while
(n--
)
107
{
108
init ();
109
while
(getline (cin, s))
110
{
111
if
(s[
0
] ==
'
\0
'
)
break
;
112
istringstream sin (s);
113
sin >>
name;
114
int
len = strlen (name);
int
flag =
0
;
115
if
(name[len-
2
] ==
'
*
'
) {flag =
1
; name[len-
2
] =
'
\0
'
;}
116
else
name[len-
1
] =
'
\0
'
;
117
118
string
u =
name, v;
119
if
(M.find (u) ==
M.end ())
120
M[u] = ++
cnt;
121
re[M[u]] =
flag;
122
123
while
(sin >>
v)
124
{
125
if
(M.find (v) ==
M.end ())
126
M[v] = ++
cnt;
127
add_edge (M[v], M[u]);
128
out
[M[v]]++
;
129
in
[M[u]]++
;
130
}
131
}
132
printf (
"
Case %d: %d\n
"
, ++
cas, TopoSort ());
133
}
134
135
return
0
;
136
}
137
138
/*
139
Case 1: 1
140
Case 2: 2
141
*/
