Собственно, сабж. Дан неориентированный невзвешенный граф. Необходимо удалить некоторое кол-во рёбер, чтобы получившийся граф представлял собой две компоненты связности, являющиеся полными. Как это сделать? Возможно ли решение за О(V+E)?

Может быть, есть ещё какие-то идеи решения... а сама задача такая:
Есть N человек, которых нужно усадить за два стола с неограниченным кол-вом мест. Есть M пар человек, которых нельзя садить за один стол. По данным N, M и самим парам человек вывести возможную рассадку людей по столам.

Моя идея решения: создаём полный неориентированный граф из N вершин. Удаляем M рёбер (те, что вводятся). А дальше производим нечто, описанное мной в первом абзаце (думаю, это какой-нибудь необычный dfs или поиск компоненты связности).

Никто не знает графы?...

Понятно.

Сахават Юсифов, как минимум, это возможно перебором, но медленно. В общем, какое-то решение есть, и мне бы было вполне достаточно узнать, какой(ие) алгоритм(ы) можно применить или, если он какой-нибудь нестандартный, хотя бы очень общую идею алгоритма. (пусть даже, если несколько медленней O(V+E))

P.S. В общем-то, учитывая мой (несколько ниже среднего) уровень знаний по алг. (спорт.) программированию, складывается (возможно, ошибочное) впечатление об уровне обитателей форума. (или, может быть, я написала не в тот раздел? Хотя, насколько я помню, где-то здесь уже обсуждались олимпиадные задачи, по-моему, это была задача про заполнение озёр)

Спасибо всем, кто хотел помочь, задачу решила. Она оказалась на удивление простой :) оказывается, я мыслила совсем не в ту сторону и достаточно раскрасить все вершины в два цвета, чтобы никакие две соединенные не были одного цвета, простейший dfs с двумя доп. условиями.