題目：http://www.lydsy.com/JudgeOnline/problem.php?id=1529
很DT的一道題谱醇，被卡了好幾次空間，最后改了手寫棧另外重復(fù)利用了一個(gè)數(shù)組才過撕彤。塘砸。。。
思路很簡(jiǎn)單需五，縮一下SCC，然后統(tǒng)計(jì)一下有幾個(gè)入度為0的點(diǎn)就可以了轧坎。。
代碼：
#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 ;
}
