[Ленивица]

Здравствуйте. Вот возникла роблемка с задачкой.

Пусть задано конечное множество имен жителей некоторого города, причем для каждого жителя перечислены имена его детей. Перечислите все пары жителей города, которые являются родственниками, причем жители А и Б называются родственниками, если:
a) А – это ребенок Б;
b) Б – это ребенок А;
c) существует некий В такой, что А является родственником В, а В является родственником Б

Как это написать?
Если вдруг тему не там создала, сорри. Очень нужна помощь.

[AlexSku]

1) структура (если отойти от множеств) - это всем знакомое [генеалогическое] дерево, где множество корней (узлы уровня 0) - это предки всех детей. Условия а) и б) связывают узлы одним ребром (по терминологии графов), т.е. уровень (терминология TreeView) родителя на 1 больше уровня ребёнка. Из условия с) следует, что всегда есть путь от А к Б через В, причём получается, что сначала к узлам В причисляются ближайшие к А и Б, потом более отдалённые, в итоге весь промежуточный путь от А к Б - это узлы В. Итак на уровне 0 будет несколько ветвей (деревьев). Берёте первое дерево и все узлы на нём - родственники между собой. Т.е. неродственники - только те, у которых разные предки уровня 0.

2) Как сформировать дерево? Один из способов - завести базу данных. Стандартные поля: номер узла, номер узла родителя (если родителя нет, то null), название (имя). Далее селекты.

[Grunch]

Думаю, можно обойтись обычным графом. Тянуть сюда БД - лишнее.
Структура узла:

Код:

TNode: record
  Name: string;
  Parents: Array of ^TNode;
  Sons: Array of ^TNode;
end;

1. Заполняем массив (или список) жителей. Для каждого жителя ищем родителей. Потомки нам известны по условию задачи.
2. Собственно для решения все готово. Берем первого жителя и выбираем всех из списков Parents и Sons. После чего для каждого из них повторяем эту процедуру. Набирается список родственников 1-го жителя.
3. Повторяем пункт 2 для тех кто еще не попал в родственники.
4. и т.д.

[Ленивица]

Спасибо огромное за помощь