\(2020\) 年 \(3\) 月 \(17\) 日更博報告：
1 月的更新雖然完善了一些問題，但是講得比較快，有些同學看不大懂，故再次更新，還有什麼不懂的請私信我。
由于阿裡雲的各種問題，使得原本在部落格園中排版精美的源碼在這裡醜陋不堪。故更好的閱讀效果請點選這裡
\(2020\) 年 \(9\) 月 \(5\) 日更博報告：
士别三日，刮目相待。更新一些細節的描述，優化排版。希望這篇題解能夠幫助更多初學者，成為最好的題解。
文字講解
題目分析：
首先 ，要知道這道題是 \(Topo\) 拓撲排序。不妨先從拓撲排序定義下手，分析題目的性質。經分析得：
食物鍊中的生物 —— 節點
生物之間的關系 —— 有向邊
為了友善描述，我們将
不會捕食其他生物的 生産者 叫做 最佳生産者
不會被其他生物捕食的 消費者 叫做 最佳消費者
由于資料中不會出現環，是以 最大食物鍊 即 左端是 最佳生産者 ，右端是 最佳消費者 的路徑
而 隻要最左端是 最佳生産者 的路徑（即最右端可以不是 最佳消費者 的最大食物鍊） 我們稱之為 類食物鍊
既然 食物鍊中的生物 可以看成 節點，那麼 最佳生産者 的入度一定為 \(0\)， 而 最佳消費者 的出度也為 \(0\)
思路引導
想要找到一條 最大食物鍊 ，那麼這條路徑的 起點 入度要為0，終點 出度要為0。 故：
既要記錄入度，還要記錄出度！
現在的問題轉換成了，如何找到圖中所有 左端點入度為0 且 右端點出度為0 的路徑的數量
正解
我們拿起筆，在草稿紙上畫一個圖進行推算。接下來将使用 樣例 進行舉例。
(将 最佳生産者 塗上 藍色，最佳消費者 塗上 紅色)
發現： 答案為 到所有 紅色點 的路徑條數的 總和
（這裡的 路徑條數總和 不是 連向它有幾條邊 ，而是以它結束的 最大食物鍊 數量的總和）
對于上圖，\(5\) 号點的對應路徑數量 取決于：以 到 \(5\) 号點的三個點（ \(2\) 号、\(3\) 号、\(4\) 号） 結尾的 類食物鍊 條數的總和。
而 以 \(2\) 号、\(3\) 号、\(4\) 号 結尾的 類食物鍊 取決于：以 可以到達 \(2\) 号、\(3\)号、\(4\)号點 的點 結尾的 類食物鍊 條數的總和。
以此類推，顯然對于 以 任一點 結尾的 類食物鍊 的數量，都取決于 藍色點
各點數量對應關系在下圖用綠色邊标注
重點：
使用拓撲排序，由題意得知 \(Topo\) 排序第一輪被删掉的點 一定是 藍色點（最佳生産者），而令 藍色點 的答案為 \(1\)。
當第一輪删點時，将藍色點可以到的點 的答案 都加上 藍色點的 答案（即加 \(1\)）。
即：拓撲排序 需要删除的點的答案 都累加到 它可以到達的點 上面去
這樣我們就将邊的累加 轉換到了 點之間的累加。
最後累加所有 紅色點（最佳消費者） 的答案，輸出即可。
以第 i 号點結束的 類食物鍊 數量 = 以 可到達 i 号點 的點 結尾的 類食物鍊 數量的和
以下是模拟操作過程：
加載時間較慢，請稍等
第一輪：删除 \(1\) 号藍色點，\(1\) 号藍色點可以到的點（\(2\) 号點、\(3\) 号點）都加 \(1\)
第二輪：删除 \(2\) 号點，\(2\) 号點可以到的點（\(3\) 号點、\(5\) 号紅色點）都加 \(1\)。此時 \(3\) 号點答案為 \(2\)，\(5\) 号點答案為 \(1\)
第三輪：删除 \(3\) 号點，\(3\) 号點可以到的點（\(4\) 号點、\(5\) 号紅色點）都加 \(2\)。此時 \(5\) 号點答案為 \(3\)，\(4\) 号點答案為 \(2\)
第四輪：最後删除 \(4\) 号點，\(4\) 号點可以到的點（\(5\) 号紅色點）加 \(2\)，此時 \(5\) 号點答案為 \(5\)
可見全圖隻有 \(5\) 号一個紅色點，那麼答案就是 \(5\) 号點的答案—— \(5\) 了
那麼代碼實作就很簡單了！
上代碼：
#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define ll long long
#define rg register
#define New int
//上面這些花裡胡哨的東西請忽略
using namespace std;
inline New read()//快速讀入
{
New X = 0,w = 0;
char ch = 0;
while(!isdigit(ch))
{
w |= ch == '-';
ch=getchar();
}
while(isdigit(ch))
{
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
char F[200] ;
inline void write(New x) //快速輸出
{
if(x == 0)
{
putchar('0');
return;
}
New tmp = x > 0 ? x : -x;
int cnt = 0;
if(x < 0)
putchar( '-' );
while(tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while(cnt > 0)
putchar(F[--cnt]) ;
}
const int N = 5e3 + 2; //定義常量大小
const int mod = 80112002; //定義最終答案mod的值
int n, m; //n個點 m條邊
int in[N], out[N]; //每個點的入度和出度
vector<int>nei[N]; //存圖，即每個點相鄰的點
queue<int>q; //拓撲排序模闆所需隊列
int ans; //答案
int num[N]; //記錄到這個點的類食物連的數量，可參考圖
signed main()
{
n = read(), m = read();
for(rg int i = 1; i <= m; ++i)
{ //輸入邊
int x = read(), y = read();
++in[y], ++out[x]; //右節點入度+1,左節點出度+1
nei[x].push_back(y); //建立一條單向邊
}
for(rg int i = 1; i <= n; ++i) //初次尋找入度為0的點(最佳生産者)
if(!in[i])
{ //是最佳生産者
num[i] = 1; //初始化
q.push(i); //壓入隊列
}
while(!q.empty())
{ //隻要還可以繼續Topo排序
int tot = q.front();//取出隊首
q.pop();//彈出
int len = nei[tot].size();
for(rg int i = 0;i < len; ++i)
{ //枚舉這個點相鄰的所有點
int next = nei[tot][i]; //取出目前枚舉到的點
--in[next];//将這個點的入度-1(因為目前要删除第tot個點)
num[next] = (num[next] + num[tot]) % mod;//更新到下一個點的路徑數量
if(in[next] == 0)q.push(nei[tot][i]);//如果這個點的入度為0了,那麼壓入隊列
}
}
for(rg int i = 1; i <= n; ++i) //尋找出度為0的點(最佳消費者)
if(!out[i]) //符合要求
ans = (ans + num[i]) % mod;//累加答案
write(ans);//輸出
return 0;//end
}