LuoguP3183 [HAOI2016]食物链 记忆化搜索

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 

#define in1(a) a=read()
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,c,d) in2(a,in2(c,d)
#define out(a) printf( "%d",a ) 
#define outn(a) out(a),putchar(‘n‘)

#define I_int int 
inline I_int read() {
    
    I_int x = 0,f = 1 ; char c = getchar() ;
    while( c < ‘0‘ || c > ‘9‘ ) {
        if( c == ‘-‘ ) f = -1 ;
        c = getchar() ;
    }
    while( c >= ‘0‘ && c <= ‘9‘ ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    return x * f ;
}
#undef I_int

using namespace std ;

#define N 100010

int n,m ;
int in[ N ],out[ N ] ;
int head[ N ],cnt ;
struct node {
    int to,nxt ;
} e[ N << 1 ] ;

void ins( int u,int v ) {
    e[ ++ cnt ].to = v ;
    e[ cnt ].nxt = head[ u ] ;
    head[ u ] = cnt ;
}

int f[ N ] ;

int dfs( int x ) {
    if( f[ x ] ) return f[ x ] ;
    int ans = 0 ;
    if( !out[ x ] && in[ x ] ) ans ++ ;
    for( int i = head[ x ] ; i ; i = e[ i ].nxt ) {
        ans += dfs( e[ i ].to ) ;
    }
    f[ x ] = ans ;
    return ans ; 
}

int main() {
    in2( n,m ) ;
    for( int i = 1,u,v ; i <= m ; i ++ ) {
        in2( u,v ) ; ins( u,v ) ;
        in[ v ] ++ ; out[ u ] ++ ;
    }
    int ans = 0 ;
    for( int i = 1 ; i <= n ; i ++ ) {
        if( !in[ i ] ) ans += dfs( i ) ;
    }
    outn( ans ) ;
}