Max Food-Chains Count

Problem Statement

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

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

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

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

Input

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

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

Output

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

Sample Input

Sample Output

1

5

Constraints

各测试点满足以下约定：

数据中不会出现环，满足生物学的要求。

Solving

类树形DP问题，将所有入度为0的点进行拓扑排序，定义dp[i]为生产者到达第i个顶点的链条数量，沿途不断更新dp[i],其状态转移方程为

$$ dp[v] = (dp[u] + dp[v]) \% MOD $$

其中每个生产者初始化dp[i] = 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


const int N = 5e3+10;
const int M = 5e5+10;
const int MOD = 80112002;
int de[N];//入度
int deout[N];//出度
int dp[N];//dp[i]表示从生产者到节点 i 的食物链数量
int head[N];
int cnt = 0;
int n,m;
int ans;
struct node
{
    int from,to,next;
}edge[M];
void add(int u,int v)
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].from = u;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
void solve()
{  
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin >> u >> v;
        de[v]++;
        deout[u]++;
        add(u,v);
    }    
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(de[i] == 0)
        {
            dp[i] = 1;
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i=head[u]; i; i=edge[i].next)
        {
            int v = edge[i].to;
            dp[v] = (dp[v] + dp[u]) % MOD;
            de[v]--;
            if(de[v] == 0)
            {
                q.push(v);
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(deout[i]==0) ans = (ans + dp[i]) % MOD;
    }
    cout << ans % MOD;
}