程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj1060,poj1094--拓撲排序

zoj1060,poj1094--拓撲排序

編輯:C++入門知識

題意描述:
給定字母表的前n個大些字母,以及這些字母間兩兩之間的大小關系(這樣的關系給定m組),問由這m組關系能否確定n個字母的整體順序,如果能輸出按續排列的字母。
顯然,本題就是拓撲排序,不過題目的要求使得我們要處理一些細節。
下面我先說以下拓撲排序:
嚴蔚敏《數據結構》上的定義是:由某個集合上的一個偏序得到該集合上的一個全序,這個操作稱之為拓撲排序。
直觀的說偏序指集合中僅有部分成員之間可比較,而全序指集合中全體成員之間均可比較。
舉個例子,一個大的工程通常有許多小的工程組成,這些小工程之間通常存在某些先後順序;當然有些小工程之間不存在先後關系,它們是可以並行的。如果兩個小工程直接或間接的相互依賴,就是兩個小工程互為對方的先行條件,整個工程將無法進行下去。用一個個頂點分別表示這些小工程,用有向的邊表示小工程之間的依賴關系,我們可以得到一個有向圖。
拓撲排序可以幫助我們確定這些小工程開始的順序,並且能夠判定小工程之間是否存在相互依賴(圖中是否有回路)。
拓撲排序的具體做法是:
1.在有向圖中選擇一個沒有前驅(入度為0)的頂點,輸出
2.從圖中刪除該頂點和所有以它為尾的弧,並更新相關點的入度
3.重復1,2步,直到所有頂點都被輸出,或者發現圖中存在回路。
如果結合上面所舉的工程的例子,沒有依賴(先後)關系的工程是可以並行的,但是就本題(zoj1060)而言,它要求每兩個點之間的關系都是確定的,是不允許出現並行的,所以,當某一時刻,我們發現入度為0的點不止1個時,排序就失敗了。
本題的輸出分為三種情況,並且要求輸出所用的條件個數,因此每增加一個條件就要做一次拓撲排序。
以下是本題代碼,第一次寫,有點亂,將就一下把~~

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved