Здравствуйте, помогите пожалуйста сделать задание на рекурсию. Ломаю голову над ней уже очень долго.

Задача:

Задано конечное множество имен жителей некоторого города, причем для каждого из жителей перечислены имена его детей. 
Жителей X и Y называются родственниками, если(а) либо X - ребенок Y, (б) либо Y - ребенок X, (в) либо существует некоторый Z, такой, что X является родственником Z, а Z является родственником Y. 
Перечислите все пары жителей города, которые являются родственниками.

___________________________

Задание нужно выполнить без использования массивов, структур.
Разрешено только посимвольное чтение из файла.

Пример входного файла:

маша(гриша, саша)
саша(ваня)
даша(маша)
костя(илья)
ваня(митя)


Выходной файл:

маша и гриша
маша и саша
гриша и саша
маша и ваня
гриша и ваня
саша и ваня
саша и митя
маша и митя
гриша и митя
и так далее

____________________

Помогите плз написать поиск строк, которые являются родственными.
Я буду очень благодарна.

вы уверены, что вам на С++ решение надо?
я помню давным давно реализовывал подобную задачу то ли на Lisp, то ли на Prolog

да, нужно на с++.

вам нужно будет решить задачу связности. Connectivity problem.
удачи 

Вы в этом уверенны ? 
задача решается через построение графа(древа родственников), который без использования структур не представляем.

Вы в этом уверены? 
я прекрасно помню, как решал аналогичную задачу используя массив. не структуру. массив правда был семантически равнозначен дереву. но не графу.

Должна получиться вот такая динамическая структура :


массивом тут и не пахнет  

Можно конечно хранить в массиве, а при обходе строить список родственной линии.
Разница будет в том, что при первом варианте сразу строится готовое древо, которая не будет иметь лишних затрат на обход, А во втором, для каждой пары родстванников вновь и вновь будет строится подходящая ветвь.


Это сообщение отредактировал(а) mes - 24.6.2009, 10:25

не обязательно.
можно сопоставить именам индексы массива.
было:

стало:

ну а дальше уже решить задачу свзяности. используя две абстрактные операции: объединение/поиск.

Это сообщение отредактировал(а) zim22 - 24.6.2009, 10:23

Я разве утверждал что мое решение единственное?


А в результате то же самое древо. Только хранимое не как связанный список, а как массив связанных индексов.

И в том и в другом случае нарушается условие:

не строиться, а перестраиваться. и это будет делаться очень быстро.


Это сообщение отредактировал(а) zim22 - 24.6.2009, 10:34

Господа, вы не забыли, что топикстартеру нужно решить эту задачу через рекурсию?   
2 Jime: какая то структура данных в любом случае понадобится. По крайней мере надо хранить исходный файл в удобном для обработке виде. Хотя можно и не хранить, а перечитывать его каждый раз   

Главная функция - принимает 2 имени и выдает флаг - родственники они или нет
Остается только вопрос - является ли человек родственником сам себе?

нет, хотя бы потому, что "нельзя" составить пару :



а я и не видел    спасибо, что обратили внимание 


Это сообщение отредактировал(а) mes - 24.6.2009, 11:45

Не факт, про 'пару жителей' тоже вопрос открытый - может ли эта 'пара' состоять из одного и того же человека в 2х экземплярах?  
Если это запретить, то в начало функции is_relatives надо добавить

Всем спасибо