#25514: Tarjan + 拓樸 + greedy


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.218.50]
最後登入時間 :
2024-05-17 10:36:18
f167. m4a1-社團 Club -- TOI練習賽2020年4月潛力組 | From: [61.230.1.56] | 發表日期 : 2021-05-28 09:46

使用拓樸排序,由於要讓字典續最小,拜訪順序為n->1,這樣n較大的會到比較後面

在拓樸的dfs中,要讓adj[n]先拜訪小的,這樣n較小的會到前面,可以使用priority_queue搭配adjacency list

要判斷圖中有沒有環,可以使用Tarjan來判斷,找到環就可以直接exit

 
ZeroJudge Forum