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