座位的人在一個禮堂算法 - 不工作那麼好

Question

考慮以下問題：

we have participants and we want to place them in an auditorium, where 
each of the participants has a list of the people that he/she don't 
want to sit behind that person , or at the same line of that person . 
We do not have any restriction regarding the number of lines in the auditorium ,or the number of seats. 

我需要寫一個算法，其中每個人都是幸福的。

我在考慮拓撲排序，我們把問題拋給圖論的領域： *在圖G =（V，E）上運行拓撲排序。 *如果有問題的排序 - 返回'是'，否則返回'否'。 該算法的工作原理如下： 在每一行中我們只放置一個參與者，第一行包含第一個參與者（他將成爲TopSort中的第一個頂點），第二行包含第二個參與者等。 如果participant A不想坐在後面（或在同一行）participant B那麼我們將有一個從A到B的有向邊，表示A位於B的後面。

我的問題開始時A不希望在同一行坐如B（或身後），並B不希望坐在後面A（或在同一行）。

我會很感激你的幫助， 問候，羅恩

Answer 1

顯然，如果有一個循環依賴（A希望B前坐下，並B希望A前坐），這個問題無解。拓撲排序似乎是解決您的問題的充分方法。