網頁

2014年3月10日 星期一

POJ 1094 Sorting It All Out

題意:
    給定N表示有N個點,M表示底下有M行關係式,然後一行一行讀取關係式:

  • 如果在第i行發現已經能明確將所有點排出順序(也就是只有一種答案),輸出Sorted sequence determined after i relations: ...(順序)
  • 如果在第i行發現和之前的關係式有衝突(形成一個環,例如A>B>C>A),則輸出Inconsistency found after i relations.
  • 如果讀取到最後關係都沒有衝突但也找不到唯一答案,則輸出Sorted sequence cannot be determined.
想法:
    每次讀取關係式的時候就檢查是否有衝突(形成一個環),如果沒有再去找topological sort,topological sort這function裡面要判斷是否為唯一解,因此只能選一條路徑往下遞迴,最後判斷答案優先順序為1.先看有沒有衝突2.看有沒有解,再依題目敘述輸出即可,詳細看底下code。