437. Предки

Исследовав гены нескольких тысяч людей, ученые предположили, что все человечество произошло от небольшого племени из 20 человек, жившего где-то в западной Африке.

Организация Association of Cloned Martians решила провести аналогичные исследования для жителей Марса. Напишите программу для ACM, которая, используя результаты большого генетического исследования марсиан, определит для каждого марсианина его прародителя.

Вход. В первой строке ввода содержится количество n (1 < n ≤ 10⁵) обследованных марсиан. Далее следует n строк, содержащих по одному целому числу от 0 до n. В (i + 1)-ой строке находится номер родителя i-го марсианина или 0, если у него нет родителя (то есть он является прародителем, как Адам или Ева в Библии). Входные данные не содержат циклов.

Выход. Вывести для каждого марсианина номер его прародителя или 0, если он является прародителем.

Пример входа	Пример выхода
7 3 3 6 7 4 0 0	6 6 6 7 7 0 0

РЕШЕНИЕ

система непересекающихся множеств

Анализ алгоритма

Воспользуемся системой непересекающихся множеств. Для каждого ориентированного ребра u → v проведем объединение множеств, содержащих u и v. В функции Union линк с представителя u следует перебросить на представителя v. Только в таком случае если вершина является прародителем, то она будет представителем множества.

В таком случае прародителем вершины v будет Repr(v). Если v = Repr(v), то вершина v сама является прародителем и в этом случае следует вывести 0.

Пример

Граф из примера имеет следующий вид:

Марсиане номер 6 и 7 являются прародителями.

Реализация алгоритма

Объявим массив mas предков, который будет использоваться в системе непересекающихся множеств..

#define MAX 100010

int mas[MAX];

Функция Repr возвращает представителя множества, содержащего вершину n.

int Repr(int n)

{

if (n == mas[n]) return n;

return mas[n] = Repr(mas[n]);

}

Функция Union объединяет множества, содержащие вершины x и y.

void Union(int x, int y)

{

int x1 = Repr(x), y1 = Repr(y);

mas[x1] = y1;

}

Основная часть программы. Инициализируем массив mas.

scanf("%d", &n);

for (i = 1; i <= n; i++)

mas[i] = i;

Предком вершины i является v, если v ≠ 0. Объядиняем множества, содержащие v и i (при v ≠ 0). В функции Union линк с представителя i следует перебросить на представителя v. Только в таком случае если вершина является прародителем, то она будет представителем множества.

for (i = 1; i <= n; i++)

{

scanf("%d", &v);

if (v != 0) Union(i, v);

}

Прародителем вершины i является вершина Repr(i). Если i = Repr(i), то вершина i сама является прародителем и в этом случае следует вывести 0.

for (i = 1; i <= n; i++)

{

father = Repr(i);

if (i == father) father = 0;

printf("%d\n", father);

}