47 lines
2.0 KiB
C++
47 lines
2.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 5005; //生物种类上限
|
||
const int M = 500005; //吃与被吃的关系数上限
|
||
const int MOD = 80112002; //最大食物链数量模
|
||
int n; //生物种类
|
||
int m; //吃与被吃的关系数
|
||
int ans; //为最大食物链数量模上 80112002 的结果
|
||
vector<int> edge[N]; //保存DAG图的邻接表
|
||
queue<int> 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;
|
||
} |