Помощь
Хау, народ)
Имею задачу, которую не знаю как решить. Гуглеж заводит или не туда, или в такие дикие дебри, что у меня отказывают пониматоры.
Собственно, воть она:
Дано:
N пар объектов вида X->Y. Объекты в парах могут повторяться.
Пример этих пар:
Требуется:
1. Построить цепь из этих объектов таким образом, что:
Цепь может иметь ответвления (когда в нескольких парах один и тот же одинаковый второй объект) и кольца.
Пример цепи, построенной из вышенаписанных пар:
Собственно, прошу ткнуть меня носом в подходящий алгоритм или их комбинацию. Или еще как-то наставить на путь истинный...
Имею задачу, которую не знаю как решить. Гуглеж заводит или не туда, или в такие дикие дебри, что у меня отказывают пониматоры.
Собственно, воть она:
Дано:
N пар объектов вида X->Y. Объекты в парах могут повторяться.
Пример этих пар:
A->С B->A C->E D->E E->B F->A G->C
Требуется:
1. Построить цепь из этих объектов таким образом, что:
а) Второй объект в каждой паре является первым объектом в следующей
б) Объекты не повторяются
в) Направление стрелок предпочтительно слева направо, но в целом не имеет значения
г) Цепь должна быть максимальной длины
б) Объекты не повторяются
в) Направление стрелок предпочтительно слева направо, но в целом не имеет значения
г) Цепь должна быть максимальной длины
Цепь может иметь ответвления (когда в нескольких парах один и тот же одинаковый второй объект) и кольца.
Пример цепи, построенной из вышенаписанных пар:
F
|
V
D->E->B->A->С<-G
^ |
|________|
Собственно, прошу ткнуть меня носом в подходящий алгоритм или их комбинацию. Или еще как-то наставить на путь истинный...
