a324. TOI 2019/05 潛力組：巨額獎金

題目描述

一款遊戲有 N 個階段，編號為 0 至 N−1。玩家從階段 0 出發，在每個階段選擇一個事件，沿著該事件移動到下一個階段，最後到達階段 N−1。事件具有方向：事件 (i, j) 代表由階段 i 前往階段 j。

原題保證玩家不會回到已經經歷過的階段；無論選擇哪些事件，遊戲都從 0 開始並在 N−1 結束；至少有一條完整路線；同一對階段之間不會重複提供事件。

公司需要知道所有從起點到結局的不同路線總數 R。請計算並輸出這個數字。原題圖例與範例 2 相同，共有 7 條路線。

輸入格式

第一行為正整數 N、E，分別代表階段數與事件數。接下來 E 行，每行包含兩個整數 i、j，表示從 i 到 j 的事件，階段編號介於 0 與 N−1。

評分段落給出的完整階段數範圍為 2≤N≤10^6。事件數的原文限制為「S−1≤E≤2×S」，但原題並未定義 S；本稿保留此疑義，不擅自將 S 改成 N。

分組：10 分滿足 2≤N≤10^2；30 分滿足 2≤N≤5×10^4；60 分滿足 2≤N≤10^6。

輸出格式

輸出一個正整數 R，表示從階段 0 到階段 N−1 的路線總數。原題沒有要求取餘數，也沒有給出 R 的上界。

原題待釐清事項

• 事件數限制使用未定義的 S，待官方確認。
• 答案 R 的數值上界未提供，不得自行增加32位元或64位元保證。

本稿僅供待審，不自行修補以上規格。

範例 1

輸入：

9 12
0 1
0 2
0 3
0 5
0 7
3 4
1 4
4 6
7 6
6 8
2 8
5 8

輸出：

5

範例 2

輸入：

10 14
0 1
0 2
1 3
1 4
1 5
1 6
2 6
3 9
4 9
5 9
6 7
6 8
7 9
8 9

輸出：

7

來源

TOI 2019/05 練習賽潛力組〈巨額獎金〉。依官方原題 PDF 自行整理，所有範例均取自原件。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201905/A2-Bonus(Q).pdf