xfstart07
Get busy living or get busy dying

/*
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)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理