a298. TOI 2026/05 潛力組：安裝順序

題目描述

有 N 套軟體，編號 1 到 N。每個相依關係 (a,b) 表示必須先安裝 a，才能安裝 b。每套軟體恰好安裝一次。已知至少存在一個合法的完整安裝順序，請判斷合法順序是否超過一種。

輸入格式

第一行有 N、M。接著 M 行各有 a、b，表示一項相依關係。

• 2 ≤ N ≤ 200000
• 1 ≤ M ≤ min(N(N−1)/2,200000)
• 1 ≤ a、b ≤ N，a ≠ b
• 相依關係不重複，且保證有合法安裝順序。

輸出格式

若存在多種合法順序，輸出 1；若恰好一種，輸出 0。

來源

TOI 2026 年 5 月潛力組〈安裝順序〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202605/Dependency.pdf