@boyar

Требуется разбить неориентированный граф на два полных графа, то есть чтобы в результате получилось 2 графа, каждая вершина которого смежна с любой другой вершиной это графа. Ничего не приходит в голову, кроме как прямой перебор в лоб, но нужен алгоритм по-оптимальней. Подскажите, пожалуйста, в каком направлении копать.

0

@Shamil1

Кто-то гарантирует, что такое разбиение существует?

0

@boyar

Пардон, задание не до конца озвучил.

... либо вывести сообщение о том, что такое разбиение невозможно.

0

@salam

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

0

@Shamil1

Видимо, операция "разбить" подразумевает удаление "лишних" рёбер. Например, полный граф всегда можно разбить на два полных подграфа, так как любой подграф будет полным.

0

@edwin_paco

Была похожая задача в контексте Яндекса, там в графе с n вершинами нужно было проверить можно ли его разбить на два полных подграф без общих вершин, используя при этом все вершины начального. Я написал что-то такое. Создаём два множества, ищем две точки у которых нет ребра, то есть они в разных подграфах и пушим в эти два множества(это будущие полные подграфы). Затем для каждой точки графа смотрим можем ли мы ее докинуть в какое-то множество, то есть нам надо проверить содержится ли одно множетсво в множестве инцедентных вершин этой точки(тип для полного графа все дела тыр пыр). Если точку можно докинуть в два графа одновременно, то закинем ее в какую-то очередь например, пока мы не рассмотрим все простые точки вот. Ок, все точки рассмлтрены, выфигачиваем точку из очереди и если она все ещё добавляема в два графа то кидаем ее в эти два графа, когда появляется точка которая протеворечит данной точке (которая лежит в двух множествах) то мы просто выпиливаем протеворечивую точки из множества, в которую мы не можем запихнуть текущую точку и спокойно ее туда пихаем. Собственно вроде все. А ну да, если протеворечивая точка не содержится в двух множествах одновременно, то все, гг.
Это все что я смог придумать на контексте, я закодил, но поймал TL на 5 тесте. Я конечно реализовывал коряво, а времени не оставалось, просто я хз как по другому(если мой вариант конечно правильный)
Могу кинуть код потом

0