Задача g6_1024: Знакомые

Имеется 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 -- если нельзя.

Решение g6_1024:
Очередная задача со школьной OL11 (составитель М.Ю. Надточий).
Идея состоит в том, чтобы разделить людей на три части:
1)толпа - в ней стоят еще никуда не поставленные люди.
2)группа №1.
3)группа №2.
Возьмем первого человека из толпы и поставим его в одну из групп, при этом вычеркнув из толпы. Выберем всех знакомых ему людей и поставим их в другую группу. Затем для каждого из этих людей найдем его знакомых и поставим их в другую группу. На каждом шаге будем проверять, не оказался ли один и тот же человек сразу в двух группах, если оказался, то ответ NO. Такой способ дает нам гарантию, что два знакомых человека не будут в одной группе, например если два знакомых между собой человека знакомы третьему, то они оба окажутся сначала в одной группе, а затем, когда их знакомые будут переставляться в другую группу они окажутся и в другой группе.
А что делать, если в двух группах находятся незнакомые люди, а толпа еще не опустела? Тогда нужно выбрать любого человека и поставить его в любую группу (если он до сих пор в толпе, значит он не знаком ни с кем из поставленных в группы.
Главное правильно организовать проверки на то, не находится ли один человек в двух группах, и на изменение состава толпы при выборе случайного человека.
Чуть не забыл! Ответ YES надо выводить, когда толпа опустела, и каждый человек находится только в одной группе. Упс :)
Все!