题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4562
好像，一年前，不知道啥叫拓扑图DP的时候做过，记得只有暴力分30。。。
显然和拓扑排序有关，实际上，可以用DP求解。设dp[i]表示以结点i结尾的食物链条数，显然dp[i]=sum{dp[j]}，其中要求存在边<j,i>。
真正的难点在于理解题意，一个是统计完整的食物链，一个是孤立的点不算，所以那些入度为0，出度也为0的不能计算。
1 #include <cstdio> 2 #include <queue> 3 4 using namespace std; 5 6 inline int get_num() { 7 int num = 0; 8 char c = getchar(); 9 while (c < '0' || c > '9') c = getchar(); 10 while (c >= '0' && c <= '9') 11 num = num * 10 + c - '0', c = getchar(); 12 return num; 13 } 14 15 const int maxn = 1e5 + 5, maxm = 2e5 + 5; 16 17 int head[maxn], eid; 18 19 struct Edge { 20 int v, next; 21 } edge[maxm]; 22 23 inline void insert(int u, int v) { 24 edge[++eid].v = v; 25 edge[eid].next = head[u]; 26 head[u] = eid; 27 } 28 29 int ind[maxn], outd[maxn], dp[maxn]; 30 31 queue<int> q; 32 33 int main() { 34 int n = get_num(), m = get_num(), ans = 0; 35 for (int i = 1; i <= m; ++i) { 36 int u = get_num(), v = get_num(); 37 insert(u, v); 38 ++ind[v], ++outd[u]; 39 } 40 for (int i = 1; i <= n; ++i) 41 if (!ind[i] && outd[i]) {q.push(i); dp[i] = 1;} 42 while (!q.empty()) { 43 int u = q.front(); 44 q.pop(); 45 for (int p = head[u]; p; p = edge[p].next) { 46 int v = edge[p].v; 47 dp[v] += dp[u]; 48 if (!(--ind[v])) q.push(v); 49 } 50 if (!head[u]) ans += dp[u]; 51 } 52 printf("%d", ans); 53 return 0; 54 }