/*
PROG: schlnet
LANG: C++
*/
#include
<
cstdio
>
#include
<
cstring
>
#include
<
cstdlib
>
using
namespace
std;
int
N,M;
int
a[
101
][
101
],b[
101
][
101
];
bool
vis[
101
],dis[
101
][
101
];
int
d[
101
],into[
101
],outd[
101
],
in
,ou;
void
init()
{
memset(a,
0
,
sizeof
(a));
memset(b,
0
,
sizeof
(b));
scanf(
"
%d
"
,
&
N);
int
t;
for
(
int
i
=
1
;i
<=
N;
++
i){
while
(scanf(
"
%d
"
,
&
t)
&&
t){
a[i][
++
a[i][
0
]]
=
t;
b[t][
++
b[t][
0
]]
=
i;
}
}
M
=
0
;
}
void
dfs(
int
x)
{
vis[x]
=
1
;
for
(
int
i
=
1
;i
<=
a[x][
0
];
++
i){
int
j
=
a[x][i];
if
(
!
vis[j])
dfs(j);
}
}
void
fdfs(
int
x)
{
d[x]
=
M;
for
(
int
i
=
1
;i
<=
b[x][
0
];
++
i){
int
j
=
b[x][i];
if
(vis[j]
&&!
d[j])
fdfs(j);
}
}
void
solve()
{
memset(d,
0
,
sizeof
(d));
for
(
int
i
=
1
;i
<=
N;
++
i)
if
(
!
d[i]){
memset(vis,
0
,
sizeof
(vis));
dfs(i);
M
++
;
fdfs(i);
}
memset(dis,
0
,
sizeof
(dis));
for
(
int
i
=
1
;i
<=
N;
++
i)
for
(
int
k
=
1
;k
<=
a[i][
0
];
++
k){
int
j
=
a[i][k];
dis[d[i]][d[j]]
=
1
;
}
memset(into,
0
,
sizeof
(into));
memset(outd,
0
,
sizeof
(outd));
for
(
int
i
=
1
;i
<=
M;
++
i)
for
(
int
j
=
1
;j
<=
M;
++
j)
if
(i
!=
j
&&
dis[i][j]){
outd[i]
++
;
into[j]
++
;
}
in
=
ou
=
0
;
for
(
int
i
=
1
;i
<=
M;
++
i){
if
(
!
into[i])
in
++
;
if
(
!
outd[i]) ou
++
;
}
}
void
out
()
{
if
(M
==
1
)
printf(
"
1\n0\n
"
);
else
{
printf(
"
%d\n
"
,
in
);
if
(
in
>
ou) printf(
"
%d\n
"
,
in
);
else
printf(
"
%d\n
"
,ou);
}
}
int
main()
{
freopen(
"
schlnet.in
"
,
"
r
"
,stdin);
freopen(
"
schlnet.out
"
,
"
w
"
,stdout);
init();
solve();
out
();
return
0
;
}
/*
Executing
Test 1: TEST OK [0.011 secs, 2892 KB]
Test 2: TEST OK [0.011 secs, 2892 KB]
Test 3: TEST OK [0.011 secs, 2892 KB]
Test 4: TEST OK [0.011 secs, 2892 KB]
Test 5: TEST OK [0.022 secs, 2892 KB]
Test 6: TEST OK [0.011 secs, 2892 KB]
Test 7: TEST OK [0.000 secs, 2892 KB]
Test 8: TEST OK [0.011 secs, 2892 KB]
Test 9: TEST OK [0.011 secs, 2892 KB]
Test 10: TEST OK [0.022 secs, 2892 KB]
Test 11: TEST OK [0.011 secs, 2892 KB]
*/
posted on 2009-07-20 09:11
xfstart07 阅读(108)
评论(0) 编辑 收藏 引用