Задача 29: Знакомые
Имеется N человек и прямоугольная таблица знакомств А[1:N,1:N], в
которой элемент A[i,j] равен 1, если человек i знаком с человеком j,
и, соответственно, наоборот, А[i,j]=А[j,i]. Выяснить, можно ли
разбить людей на 2 группы так, чтобы в каждой группе были только
незнакомые люди.
Информация о знакомствах содержится в файле input.txt, в первой
строке которого находится число N<250, а в следующих N строках -
таблица знакомств А (без пробелов), например:
6
000101
000000
000000
100000
000000
100000
Программа должна вывести в файл output.txt одно слово: YES!, если
группы создать можно, и NO -- если нельзя.
Решение:
Очередная задача со школьной OL11 (составитель М.Ю. Надточий).
Идея состоит в том, чтобы разделить людей на три части:
1)толпа - в ней стоят еще никуда не поставленные люди.
2)группа №1.
3)группа №2.
Возьмем первого человека из толпы и поставим его в одну из групп,
при этом вычеркнув из толпы. Выберем всех знакомых ему людей и
поставим их в другую группу. Затем для каждого из этих людей найдем
его знакомых и поставим их в другую группу. На каждом шаге будем
проверять, не оказался ли один и тот же человек сразу в двух
группах, если оказался, то ответ NO. Такой способ дает нам гарантию,
что два знакомых человека не будут в одной группе, например если два
знакомых между собой человека знакомы третьему, то они оба окажутся
сначала в одной группе, а затем, когда их знакомые будут
переставляться в другую группу они окажутся и в другой группе.
А что делать, если в двух группах находятся незнакомые люди, а толпа
еще не опустела? Тогда нужно выбрать любого человека и поставить его
в любую группу (если он до сих пор в толпе, значит он не знаком ни с
кем из поставленных в группы.
Главное правильно организовать проверки на то, не находится ли один
человек в двух группах, и на изменение состава толпы при выборе
случайного человека.
Чуть не забыл! Ответ YES надо выводить, когда толпа опустела, и
каждый человек находится только в одной группе. Упс :)
Все!
Далее
ð
