第一种 ： 拓扑排序 + 链式前向星 + dp
链式前向星不会的话看我这篇博客 ： https://blog.csdn.net/weixin_43851525/article/details/90411677
说一下里面的 dp[v] += dp[u], 这个要用到动态规划的思想，这一步的结果由上一步的来决定，我们想要确定一个有向图有多少个“食物链”， 可以确定每个出度为0的点（我把它称为“最终出口”）所连食物链之和，也就是把一张图以n个最终出口为基准，拆成 n个食物链，这样的话求和就OK，不清楚的话可以自己画一张图，看看把多个最终出口的图拆分成几张图，就可以很清楚的看到动态规划的步骤了~
下面是链式前向星的AC代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; struct node { int to, next; //链式前向星操作，不懂看另一篇博客 }e[maxn << 1]; int head[maxn], in[maxn], out[maxn]; // in表示出度，out表示入度 int dp[maxn], n, m, cnt = 0, ans = 0; // dp表示动态存储以该点为终点的食物链数目 void add (int from, int to) { e[++cnt].to = to; e[cnt].next = head[from]; head[from] = cnt; // 存图 } void topsort() { queue <int> q; for (int i = 1; i <= n; i++) { if (!in[i]) { //将入度为0的点存入队列，拓扑排序的基本方法 q.push(i); if (out[i]) dp[i] = 1; //将有“出口”的点的此时的食物链条数初始化为1 } } while (!q.empty()) { int u = q.front(); //弹出 q.pop(); for (int i = head[u]; i != -1; i = e[i].next) { // 链式前向星遍历该点所连点 int v = e[i].to; in[v]--; // 删除的点的入度更新 dp[v] += dp[u]; //上面说过 if (!in[v]) q.push(v); //存入 } } for (int i = 1; i <= n; i++) { if (!out[i]) ans += dp[i]; // 将所有 “最终出口” 的食物链数目相加即为答案 } cout << ans << endl; } int main() { memset(head, -1, sizeof(head)); cin >> n >> m; for (int i= 0; i < m; i++) { int ui, vi; cin >> ui >> vi; add (ui, vi); in[vi]++, out[ui]++; } topsort(); return 0; }
下面是邻接表的AC代码，如果理解了本题原理的话邻接表就更简单了
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int head[maxn], in[maxn], out[maxn]; int dp[maxn], n, m, cnt = 0, ans = 0; vector <int> e[maxn]; void topsort() { queue <int> q; for (int i = 1; i <= n; i++) { if (!in[i]) { q.push(i); if (out[i]) dp[i] = 1; } } while (!q.empty()) { int u = q.front(); q.pop(); for (auto it = e[u].begin(); it != e[u].end(); it++) { int v = *it; in[v]--; if (!in[v]) q.push(v); dp[v] += dp[u]; } } for (int i = 1; i <= n; i++) { if (!out[i]) ans += dp[i]; } cout << ans << endl; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int ui, vi; cin >> ui >> vi; e[ui].push_back(vi); in[vi]++, out[ui]++; } topsort(); return 0; }
PS ： 一位学了四年算法的大佬说，链式前向星和邻接表相比，写法稍微麻烦，速度更快，内存节省5倍，所以具体用哪种根据自己情况来吧~
