Условная сортировка

Question

Учитывая N отношений следующего типа
например, N = 4

A> B

A> C

B> C

D> A

Расположите элемент отношения таким образом, чтобы для каждого последовательного 'xy' в расположении 'x> y'

Выходные данные вышеприведенного примера были DABC

Учитывая N <20 </p>

Отношения будут даны в двумерном массиве

Спасибо за ваше время.

Answer 1

Если есть такое решение - ваша проблема, смоделированная для графика, на самом деле представляет собой DAG .

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

Запустить топологическую сортировку и распечатать вершины по порядку.Сбой топологической сортировки IFF - решения нет, поскольку у графа есть циклы - поэтому у сущностей нет выполнимого упорядочения [наоборот, такое же повторное сопоставление].