注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

1529: [POI2005]ska Piggy banks(SCC)  

2014-01-23 14:21:00|  分类: oi,bzoj,scc |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1529


很DT的一道题,被卡了好几次空间,最后改了手写栈另外重复利用了一个数组才过。。。。

思路很简单,缩一下SCC,然后统计一下有几个入度为0的点就可以了。。



代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define MAXN 1000100

  •  

  • struct edge {

  •     edge *next ;

  •     int t ;

  • } *head[ MAXN ] ;

  •  

  • void AddEdge( int s , int t ) {

  •     edge *p = new( edge ) ;

  •     p -> t = t , p -> next = head[ s ] ;

  •     head[ s ] = p ;

  • }

  •  

  • int n , a[ MAXN ] ;

  •  

  • int dfn[ MAXN ] , low[ MAXN ] , scc[ MAXN ] , cnt = 0 , S[ MAXN ] , top = 0 ;

  • bool f[ MAXN ] ;

  •  

  • void Tarjan( int v ) {

  •     dfn[ v ] = low[ v ] = ++ cnt ;

  •     S[ ++ top ] = v , f[ v ] = true ;

  •     for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( ! dfn[ p -> t ] ) {

  •         Tarjan( p -> t ) ; low[ v ] = min( low[ v ] , low[ p -> t ] ) ;

  •     } else if ( f[ p -> t ] ) low[ v ] = min( low[ v ] , low[ p -> t ] ) ;

  •     if ( dfn[ v ] == low[ v ] ) {

  •         int u ;

  •         do {

  •             f[ u = S[ top -- ] ] = false ; scc[ u ] = v ;

  •         } while ( u != v ) ;

  •     }

  • }

  •  

  • int main(  ) {

  •     memset( head , 0 , sizeof( head ) ) ;

  •     scanf( "%d" , &n ) ;

  •     for ( int i = 0 ; i ++ < n ; ) {

  •         scanf( "%d" , &a[ i ] ) ; AddEdge( a[ i ] , i ) ;

  •     }

  •     memset( dfn , 0 , sizeof( dfn ) ) ;

  •     memset( f , false , sizeof( f ) ) ;

  •     for ( int i = 0 ; i ++ < n ; ) if ( ! dfn[ i ] ) {

  •         Tarjan( i ) ;

  •     }

  •     memset( dfn , 0 , sizeof( dfn ) ) ;

  •     for ( int i = 0 ; i ++ < n ; ) if ( scc[ a[ i ] ] != scc[ i ] ) {

  •         dfn[ scc[ i ] ] ++ ;

  •     }

  •     int ans = 0 ;

  •     for ( int i = 0 ; i ++ < n ; ) if ( scc[ i ] == i && ! dfn[ i ] ) ++ ans ;

  •     printf( "%d\n" , ans ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(0)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018