#25514: Tarjan + 拓樸 + greedy


fire5386 (Penguin07)

School : 國立清華大學
ID : 115822
IP address : [1.160.168.174]
Last Login :
2023-02-03 15:42:58
f167. m4a1-社團 Club -- TOI練習賽2020年4月潛力組 | From: [61.230.1.56] | Post Date : 2021-05-28 09:46

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

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

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

 
ZeroJudge Forum