講堂アルゴリズムの人々シーティング - 動作しませんので、良い

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）でトポロジカルソートを実行します。 *問題のソートがある場合は「はい」を返し、そうでない場合は「いいえ」を返します。 アルゴリズムは次のように動作します。 各行に1人の参加者が配置されます。最初の行は最初の参加者（TopSortの最初の頂点）を保持し、2番目の行は2番目の参加者などを保持します。 If participant Aは、背後に（または同じ行に）座ったくない場合は、participant Bを指定すると、AからBへの有向枝があり、Aは後ろにBと表示されます。 AがB（または彼の後ろ）と同一線上に座って、そしてBはA（または同じラインで）後ろに座るしたくないしたくないとき

私の問題が開始されます。循環依存関係は、（AがB前に座るしたい、とBはA前に座るしたい）がある場合、私はあなたが、助け よろしく感謝

、ロン

明らか

Answer 1

は、問題は何も解決していません。トポロジカルなソートは、あなたの問題に対する適切なアプローチのようです。