給定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。
沒有留言:
張貼留言