если по условию это можно сделать, разбить всех людей на 2 группы
то проще простого
сортируешь матрицу так что в верхней строчке оказались те у кого больше всех знакомых

берешь 1-го и выбираешь всех с кем он не знаком(ПРОВЕРЯЕШЬ ЧТО НЕ ЗНАКОМЫЕ НЕ ЗНАКОМЫ ДРУХ С ДРУХОМ), это и будет первая группа, а остальные вторая, естественно проверка должна дать, что это действительно так!

В итоге если нельзя так сделать то ответ должен быть "Разбить на 2 группы нельзя"

представь себе человека который знаком сразу с 2-мя человеками, и сразу станет все на место! Куда ты его поместишь и что делать с его знакомыми?