b240. 判定 DAG - 旦旦解題農場

內容

如標題所說，判定是否為有向無環圖 $(DAG)$ 。

輸入說明

第一列輸入兩數 $n,m$ 代表點和邊數。

接下來 $m$ 列輸入兩數 $u,v$ 代表存在一條從 $u$ 指向 $v$ 的有向邊。

輸出說明

如果為DAG，輸出"yes"，反之輸出"no"。

範例輸入

範例一:
4 3
1 2
2 3
3 4
------
範例二:
3 3
1 2
2 3
3 1

範例輸出

範例一:
yes
------
範例二:
no

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

提示：

$1\leq n \leq 2*10^{5} \; , \; 0 \leq m \leq 4*10^{5} \; , \; 1 \leq u,v \leq n $

其實這就是在考拓撲排序。

題解。

標籤:

DAG Kahn’s Algorithm 圖論拓樸排序有向無環圖

出處:

[管理者：

Pote_Liu (13th 初階助教)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」