P4017 最大食物链计数
题目传送门
一、理解与感悟
求DAG的拓扑序列有两种办法，都是可以的，一种是比较常用的BFS入度为0的思路框架求拓扑序列，另一种是DFS+记忆化的思路框架求拓扑序列，本题解都来实现一下。
总结：
1、谁向谁有一条有向边是需要强调的，x->y与 y->x是完全不同的。 本题是说x被y吃掉，记录的是这个关系，即x->y有一条有向边。
2、需要进行模的题，需要每一步操作结果时，都进行一次MOD操作，防止中间过程数据过大。
3、获得的所有食物链数量加在一起，再MOD，才是结果。
4、DAG+广度优先搜索= "拓扑排序" !!! 目的：使得在搜到点x时，所有能达到点x的点，已经被搜过了。
5、拓扑排序思路：把入度为0的入到队列，然后找到它的所有出边，对接点入度-1，如果对接点入度为0，则再入队列。
6、每一个以当前结点为终止结点的路径条数，等于上一级的N个结点，每个结点条数的和。
7、在DAG的广度搜索中+动态规划是本题的难点，注意base case的理解。
8、入度为0的，是第一批入队列的，它们是食物链的底层（草根）。出度为0的是食物链的顶层，是老虎，鹰，鲨鱼等。
9、入度是否为0，是判断是不是再继续入队列的条件。
10、出度为0的所有结点，它们的食物链条数和就是答案。另外，出度是不需要进行记录维护，因为\(edge[i].size\)就是它的出边有多少个，本身就是出度。所有网上代码中有维护出度的都是傻子。
二、广度优先遍历解法(bfs)
#include
using namespace std;
const int N = 5005; //生物种类上限
const int M = 500005; //吃与被吃的关系数上限
const int MOD = 80112002; //最大食物链数量模
int n; //生物种类
int m; //吃与被吃的关系数
int ans; //为最大食物链数量模上 80112002 的结果
vector edge[N]; //保存DAG图的邻接表
queue q; //广搜的队列
int f[N]; //每个生物种类的食物链最长值
int ind[N]; //每个生物种类的入度
int main() {
cin >> n >> m;
//m种关系
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y; //x被y吃掉
ind[y]++; //点y的入度+1
edge[x].push_back(y); //用邻接表记录下食物链的关系,x被y吃掉,由x向y引一条有向边
}
//找到所有入度为0的点，放入广度优先搜索的队列
for (int i = 1; i <= n; i++) if (ind[i] == 0) q.push(i), f[i] = 1;
//f[i]=1：base case,它到它的每个孩子都有一条出边，就是一条路径
//广度优先搜索DAG，就是拓扑排序的模板
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < edge[x].size(); i++) { //遍历所有出边
int y = edge[x][i]; //目标结点
f[y] = (f[x] + f[y]) % MOD; //在计算f[y]之前，f[x]都是计算过的了,累加
//对接点入度-1，抹去这条入边
ind[y]--;
//如果入度为0，则入队列，准备处理它
if (!ind[y]) q.push(y);
}
}
//遍历所有结点，如果出度为0，描述是食物链的顶端生物
for (int i = 1; i <= n; i++) if (edge[i].size() == 0) ans = (ans + f[i]) % MOD;
//输出大吉
cout << ans << endl;
return 0;
}
三、深度优先遍历解法（dfs）
下面的代码得分20，通过2个点，8个点TLE，看来需要优化，进入下一步，记忆化搜索
#include
using namespace std;
const int MOD = 80112002;
const int N = 500010;
int n; //生物种类
int m; //吃与被吃的关系数
vector edge[N]; //保存有向图的邻接表
int ind[N]; //每个生物种类的入度
int ans; //为最大食物链数量模上 80112002 的结果
/**
* 功能：计算以x出发点的所有食物链条数(最长链)
* @param x
* @return
*/
int dfs(int x) {
//如果当前节点没有出度，说明到了食物链顶端，就是一条完整的食物链，也就是递归的终点,需要+1了~
if (!edge[x].size()) return 1;
//遍历所有的邻接边,所有分支食物链接数量和就是当前结点的食物链数量
int sum = 0;
for (int i = 0; i < edge[x].size(); i++) sum = (sum + dfs(edge[x][i])) % MOD;
return sum % MOD; //走一步模一步
}
int main() {
cin >> n >> m;
//m种关系
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y; //被吃的生物x和吃x的生物y
edge[x].push_back(y); //用邻接表记录下食物链的关系,x被y吃掉,由x向y引一条有向边
ind[y]++; //y入度++
}
//对于每个生物，如果入度为0，表示是最底层的生物，开始进行深搜，所有的“食物链条数”
for (int i = 1; i <= n; i++) if (!ind[i]) ans = (ans + dfs(i)) % MOD;
//输出大吉
cout << ans << endl;
return 0;
}
四、深度优先遍历解法(dfs+记忆化)
可以正常AC掉此题。
#include
using namespace std;
const int MOD = 80112002;
const int N = 500010;
int n; //生物种类
int m; //吃与被吃的关系数
vector edge[N]; //保存DAG图的邻接表
int ind[N]; //每个生物种类的入度
int ans; //为最大食物链数量模上 80112002 的结果
int f[N]; //记忆化搜索的记录数组
//下面的代码得分通过记忆化搜索AC掉本题
/**
* 功能：计算以x出发点的所有食物链条数
* @param x
* @return
*/
int dfs(int x) {
if (f[x]) return f[x];
//如果当前节点没有出度，说明到了食物链顶端，就是一条完整的食物链，也就是递归的终点,需要+1了~
if (!edge[x].size()) return 1;
//遍历所有的邻接边,所有分支食物链接数量和就是当前结点的食物链数量
int sum = 0;
for (int i = 0; i < edge[x].size(); i++) sum = (sum + dfs(edge[x][i])) % MOD;
return f[x] = sum % MOD; //走一步模一步
}
int main() {
cin >> n >> m;
//m种关系
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y; //被吃的生物x和吃x的生物y
edge[x].push_back(y); //用邻接表记录下食物链的关系,x被y吃掉,由x向y引一条有向边
ind[y]++; //y入度++
}
//对于每个生物，如果入度为0，表示是最底层的生物，开始进行深搜，所有的“食物链条数”
for (int i = 1; i <= n; i++) if (!ind[i]) ans = (ans + dfs(i)) % MOD;
cout << ans << endl;
return 0;
}