Условно сортиране - алгоритъм, сортиране

Дадени N отношения от следния тип
например N = 4

A> B

A> С

B> С

D> A

Подредете елемента на връзката по такъв начин, че за всяко последователно "xy" в подреждането "x> y"

Резултатът от горния пример е DABC

Като се има предвид N <20

Връзките ще бъдат дадени в двуизмерен масив

Благодарим ви за вашето време.

Отговори:

Ако има такова решение - проблемът ви, моделиран на графика, всъщност е ДАГ.

Графиката е G=(V,E) където V= { A,B,C,D} и E = { (x,y) | x < y } = { (B,A),(C,A),(C,B),(A,D) } , [Можете, разбира се, да го удължите за по-големи възвишения, въз основа на входа].

Изпълнете a топологичен сорт, и отпечатайте върховете в ред. Топологичният сортимент на МФФ е неуспешен - няма решение, тъй като графиката има цикли - така че обектите нямат възможност за подреждане (друг начин е същият.