洛谷P3183 [HAOI2016]食物链

记忆化搜索

 

1 #include 
     
        2 #define For(i,j,k) for(int i=j;i<=k;i++)  3 using namespace std ;  4  5 const int N = 100011,M = 200011 ;  6 int n,m,cnt,ans ;  7 int f[N],head[N],IN[N],OUT[N] ;  8 struct node{ 9     int to,pre ; 10 }e[M] ; 11 12 inline int read() 13 {14     int x = 0 , f = 1 ; 15     char ch = getchar() ; 16     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 17     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 18     return x * f ;  19 }20 21 inline void add(int x,int y) 22 {23     e[++cnt].to = y ; 24     e[cnt].pre = head[x] ; 25     head[x] = cnt ; 26 }27 28 inline int dfs(int u) 29 {30     if(f[u]) return f[u] ; 31     if(IN[u]&&!OUT[u]) return f[u] = 1 ;          //  单个生物是无法成为食物链的 32     for(int i=head[u];i;i=e[i].pre) {33         int v = e[i].to ;  34         f[u]+=dfs(v) ;  35     }36     return f[u] ; 37 }38 39 int main() 40 {41     n = read() ; m = read() ; 42     int x,y ; 43     while(m--) {44         x = read() ; y = read() ; 45         add(x,y) ; OUT[x]++ ; IN[y]++ ; 46     }47     For(i,1,n) if(!f[i]) ans+=dfs(i) ; 48     printf("%d\n",ans) ; 49     return 0 ; 50 }