拓撲排序(Topological Sorting)是一個有向無環圖(DAG, Directed Acyclic Graph)的所有頂點的線性序列。 且該序列必須滿足下面兩個條件: 每個頂點出現且隻出現一次。 若存在一條從頂點A 到頂點B 的路徑,那麼在序列中頂點A 出現在頂點B 的前面。
該算法解決的問題類似于辦事的流程一樣
在做一件事情之前必須完成之前的一件或多件相關的事情

1.先在所有任務中找到沒有需要其他任務做鋪墊的任務,圖檔中展現為點1。将1先入隊,尋找其他點,在第一次尋找結束後,開始出隊,将1出隊,尋找與他相關的後面任務,解鎖後面任務的一個條件。
再次尋找目前完全解鎖條件的任務再次入隊,依次循環,直到隊空為止
假定一個工程項目由一組子任務構成,子任務之間有的可以并行執行,有的必須在完成了其它一些子任務後才能執行。“任務排程”包括一組子任務、以及每個子任務可以執行所依賴的子任務集。
比如完成一個專業的所有課程學習和畢業設計可以看成一個大學生要完成的一項工程,各門課程可以看成是子任務。有些課程可以同時開設,比如英語和C程式設計,它們沒有必須先修哪門的限制;有些課程則不可以同時開設,因為它們有先後的依賴關系,比如C程式設計和資料結構兩門課,必須先學習前者。
但是需要注意的是,對一組子任務,并不是任意的任務排程都是一個可行的方案。比如方案中存在“子任務A依賴于子任務B,子任務B依賴于子任務C,子任務C又依賴于子任務A”,那麼這三個任務哪個都不能先執行,這就是一個不可行的方案。你現在的工作是寫程式判定任何一個給定的任務排程是否可行。
輸入格式:
輸入說明:輸入第一行給出子任務數N(≤100),子任務按1~N編号。随後N行,每行給出一個子任務的依賴集合:首先給出依賴集合中的子任務數K,随後給出K個子任務編号,整數之間都用空格分隔。
輸出格式:
如果方案可行,則輸出1,否則輸出0。
輸入樣例1:
12 2 1 2 1 4 1 5 2 3 6 1 3 2 7 8 1 7 1 10
輸出樣例1:
1
輸入樣例2:
5 2 1 4 2 2 5
輸出樣例2:
一個項目由若幹個任務組成,任務之間有先後依賴順序。項目經理需要設定一系列裡程碑,在每個裡程碑節點處檢查任務的完成情況,并啟動後續的任務。現給定一個項目中各個任務之間的關系,請你計算出這個項目的最早完工時間。
輸入格式:
首先第一行給出兩個正整數:項目裡程碑的數量 N(≤100)和任務總數 M。這裡的裡程碑從 0 到 N−1 編号。随後 M 行,每行給出一項任務的描述,格式為“任務起始裡程碑 任務結束裡程碑 工作時長”,三個數字均為非負整數,以空格分隔。
輸出格式:
如果整個項目的安排是合理可行的,在一行中輸出最早完工時間;否則輸出"Impossible"。
輸入樣例 1:
9 12 0 1 6 0 2 4 0 3 5 1 4 1 2 4 1 3 5 2 5 4 0 4 6 9 4 7 7 5 7 4 6 8 2 7 8 4
輸出樣例 1:
18
輸入樣例 2:
4 5 0 1 1 0 2 2 2 1 3 1 3 4 3 2 5
輸出樣例 2:
Impossible
該代碼可以達到拓撲排序的效果,而有些題目就需要該代碼的拓展