Двудольный граф (ненаправленный)

Question

Я беру вход, например, 4 1 3 1 2 2 4

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

Пока это нормально, за исключением того, что один из графиков содержит 1 000 000 узлов. Каждый раз, когда я пытаюсь его использовать, я получаю ошибку переполнения стека, хотя я еще больше ее упорядочил и увеличил максимальный размер кучи затмения до 1024 м.

Я не спрашиваю код, просто спрашиваю, делаю ли я что-то явно неправильно, чтобы продолжать получать ошибки.

Answer 1

Может быть, вы могли бы оптимизировать свой алгоритм обнаружения цикла. Это может помочь вам: http://en.wikipedia.org/wiki/Cycle_detection

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

Answer 2

Если это двудольный график, вы всегда можете закрасить его только двумя цветами (например, первый раздел - белый, а второй - черный).

Обычно, когда кто-то думает о раскраске графа, он должен указать количество цветов. Вы всегда можете раскрасить график, назначив каждому узлу свой цвет. Другой пример: для плоских графиков требуются только четыре цвета. Однако для большинства графов [хроматическое число] графа равно [NP].

[NP] http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems

[хроматическое число] http://en.wikipedia.org/wiki/Graph_coloring

Answer 3

Ну, это ЕСТЬ полная проблема NP (самый длинный цикл), так что такого рода вещи могут произойти.

Я бы, наверное, просто снова поднял кучу и позволил ей работать ...

РЕДАКТИРОВАТЬ: не важно. получил мое сокращение назад.