[题目链接]最大食物链计数

题目背景

你知道食物链吗?Delia 生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。

题目描述

给你一个食物网,你要求出这个食物网中最大食物链的数量。

(这里的“最大食物链”,指的是生物学意义上的食物链,即最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者。)

Delia 非常急,所以你只有 1 秒的时间。

由于这个结果可能过大,你只需要输出总

数模上 80112002 的结果。

输入格式

第一行,两个正整数 n,m,表示生物种类 n 和吃与被吃的关系数 m

接下来 m 行,每行两个正整数,表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数,为最大食物链数量模上 80112002 的结果。

样例 #1
样例输入 #1
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
样例输出 #1
5
提示

各测试点满足以下约定:

【补充说明】

数据中不会出现环,满足生物学的要求。(感谢 @AKEE )

题目分析

它是一个 DAG ,并且画图发现,下一个点的答案可以从前一个点的答案转移而来。所以我们要找一种顺序,来合并这些答案。
于是可以想到拓扑排序,当该点的入度为 0 时,说明前面的点都被处理过,答案已经是最优了。

拓扑排序

对于图的拓扑排序,有一些细节。我们可以发现一张图不一定只有一个出发点,我称之为不严格拓扑排序(如果严格的话只有一种排法了,可以参考P1347排序),同样,它也有多个结束点。所以刚开始的时候要将所有入度为 0 的点都 push 进队列,在最后要统计所有出度为 0 的点的答案。

此外,我们还发现题目虽然说的是 xy 吃,但是拓扑排序,把所有边都反一下是没有问题的,不过如果在上面那个细节中没有统计完全,那么读入顺序是有区别的(亲身经历)。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MOD = 80112002;
int n, m;
const int N = 5010;
const int M = 5e5 + 10;
int dp[N];
struct edge{
  int from, to;
};
vector<int> topusplit;
vector<int> G[N];
int indeg[N], outdeg[N];
inline void topu() {
  queue<int> q;
  for(int i = 1; i <= n; i++) {
    if(indeg[i] == 0) {q.push(i); dp[i] = 1;}
  }
  while(!q.empty()) {
    int now = q.front(); q.pop();
    topusplit.emplace_back(now);
    int sz = G[now].size();
    for(int i = 0; i < sz; i++) {
      int s = G[now][i];
      indeg[s]--;
      dp[s] += dp[now];
      dp[s] %= MOD;
      if(indeg[s] == 0) q.push(s);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    if(outdeg[i] == 0) ans += dp[i], ans %= MOD;//跟开始一样,统计所有出度为0的点
  }
  printf("%d\n", ans);
}
int main()
{
  // freopen("P4017_1.in", "r", stdin);
  // freopen(".out", "w", stdout);
  scanf("%d%d", &n, &m);
  int u, v;
  for(int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    G[u].emplace_back(v);
    indeg[v]++, outdeg[u]++;
  }
  for(int i = 1; i <= n; i++) {
    dp[i] = 0;
  }
  topu();
  return 0;
}