介紹
拓撲排序，對于一個 DAG，每次去掉入度為 \(0\) 的邊，最后將圖去光，就是拓撲排序，
拓撲排序可以處理一些有序東西，比如在日常作業中，可能會將專案拆分成 \(A,B,C,D\) 四個子部分來完成，但 \(A\) 依賴于 \(B\) 和 \(D\)，\(C\) 依賴于 \(D\)（有先后順序），為了計算這個專案進行的順序，可對這個關系集進行拓撲排序，得出一個線性的序列，則排在前面的任務就是需要先完成的任務，（\(\color{white}{\texttt{感覺像是個帶依賴背包awa}}\)）
代碼實作如下：
例題
1. NOIP2013普及T4 車站分級
題目中說，如果這趟車次停靠了火車站 \(x\)，則始發站、終點站之間所有級別大于等于火車站 \(x\) 的都必須停靠，也就是說，這趟車次經過且不停靠的所有車站的級別都必須小于這趟車次停靠的所有車站的級別\(\color{white}{\texttt{awa}}\)，
可以用有向圖連接，由等級低的車站向等級高的車站連一條邊，就是從低到高的，然后做個拓撲排序再統計下等級數即可\(\color{white}{\texttt{qaq}}\)，
2. 洛谷P1437 排序
幾個增大不等式，顯然可以建圖跑拓撲，
若根據前 \(x\) 個關系即可確定這 \(n\) 個元素的順序，輸出
Sorted sequence determined after xxx relations: 順序.（順序不寫符號，直接寫字母）
若根據前 \(x\) 個關系即發現存在矛盾（如 \(A<B,B<C,C<A\)），輸出
Inconsistency found after 2 relations.
若根據這 \(m\) 個關系無法確定這 \(n\) 個元素的順序，輸出
Sorted sequence cannot be determined.
- 判第二個就是拓撲不完，也就是有環，
- 判第三個就是拓撲時拓展了多個節點，導致這些同級的東西分不清，
- 否則就是第一個，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65254.html
標籤：其他
上一篇：Anaconda 3執行conda update --all時產生">10 possible package resolutions "警告資訊是怎么回事??
下一篇：獨立機器和虛擬機