найти родственников

Задано конечное множество имен жителей некоего города,
причем для каждого из жителей перечислены имена его детей.
Жители X и Y называются родственниками ,если

a) либо X - ребенок Y
b) либо Y - ребенок X
c) либо существует некий Z такой, что X - родственник Z, а Z - родственник Y.

Перечислить все пары жителей города,которые являются родственниками.



Задача, как по мне, выше среднего уровня.

Первая проблема которая перед нами стоит - это как задать начальные данные.
Я долго думал на эту тему и пришел к выводу, что пользователю проще работать
с именами, чем с индексами соотв. имени. Поэтому я не пошел стандартным путём
(  а это задание вектора имен, потом задание вектора векоторов + вектор булевых переменных для раскраски... - муть зеленая)

Я использовал наборы из STL, т.е std::set

Для описания связи я использовал std::pair

Задав таким образом пары мы перезходим к следующей проблеме - нужно получить список уникальных имен, т.е. получить набор всех жителей. С этим отлично справился контейнер std::set.

Теперь нам нужно оценить каждого с каждым на предмет родства, это делать удобнее с std:vector - поэтому мы перегоняем данные из set в vector

Ну и самое главное - определение родства. Используем рекурсию для обхода дерева (направленный граф) для получения родственников для заданного человека, а потом ищем в нем того с чем определяем родство....


Полное решение будет стоит 250WMR. Обращайтесь.