OJ题号：BZOJ4562、洛谷3183

思路：记忆化搜索。

本体可以转化成“求有向图中入度为0的结点到出度为0的结点的路径数”。

每次加边时记录每个结点的入度和出度，然后从入度为0的结点开始搜索，搜到出度为0的结点。

搜索到越底层，重复的路径越多，所以就要用记忆化的思想，将每个结点出发的路径个数记录下来，第二次搜到时直接调用。

1 #include
     
       2 #include
      
        3 const int N=100001; 4 std::vector
       
         e[N]; 5 int in_degree[N]={
   0}; 6 void add_edge(const int a,const int b) { 7     e[a].push_back(b); 8     in_degree[b]++; 9 }10 bool isroot(const int x) {11     return !in_degree[x];12 }13 bool isleaf(const int x) {14     return !e[x].size();15 }16 int f[N]={
   0};17 int dfs(const int x) {18     if(f[x]) return f[x];19     if(isleaf(x)) return f[x]=1;20     int ans=0;21     for(int i=0;i<(int)e[x].size();i++) {22         ans+=dfs(e[x][i]);23     }24     return f[x]=ans;25 }26 int main() {27     int n,m;28     scanf("%d%d",&n,&m);29     for(int i=1;i<=m;i++) {30         int a,b;31         scanf("%d%d",&a,&b);32         add_edge(a,b);33     }34     int ans=0;35     for(int i=1;i<=n;i++) {36         if(isroot(i)&&!isleaf(i)) ans+=dfs(i);37     }38     printf("%d\n",ans);39     return 0;40 }