進階班例題

作業順序是否可行

時間限制 1000 ms · 記憶體限制 256 MB · C++

小明要完成 $N$ 項作業，部分作業有前後順序的限制，例如作業 $u$ 必須在作業 $v$ 之前完成。

請判斷是否存在一種合法的完成順序，也就是能將所有作業排序，使每個限制都滿足。

輸入說明

  • 第一行輸入兩個整數 $N, M$。
  • 接下來 $M$ 行，每行輸入兩個整數 $u, v$，表示作業 $u$ 必須在作業 $v$ 之前完成。
  • $1 \leq N \leq 10^5$
  • $0 \leq M \leq 2 \times 10^5$
  • $1 \leq u, v \leq N$

輸出說明

若存在至少一種合法順序，請輸出YES，否則輸出NO。

範例

範例輸入 1

3 2
1 2
2 3

範例輸出 1

YES

範例輸入 2

3 3
1 2
2 3
3 1

範例輸出 2

NO

範例輸入 3

4 2
1 3
2 3

範例輸出 3

YES
C++77 / 50,000

「跑範例測資」只跑題目敘述上的範例，會顯示你的輸出與正確答案的對照； 「提交評測」會跑完整的測資並給實際結果，但不會顯示測資內容。兩者都不需要帳號，也不會留下成績紀錄。