Сколько существует способов закрасить неокрашенные края в круге?

Question

дано n точек на окружности и нарисованы все ребра (C (2, n)).Некоторые из этих краев уже окрашены в синий или красный цвет.Вы должны выяснить, сколько способов можно покрасить отдохнувшими краями, чтобы получить окончательное изображение с условиями ниже:

1. все края окрашены.
2. все треугольники имеют 0 или 2 краякрасным цветом.

вот несколько примеров:

пример 1

ввод: n = 3, а число ребер 0 уже окрашено.output = 4: потому что мы можем закрасить все ребра синим или только один из них синим, а остальные красным.

пример 2

введите n = 4 и 4 числа реберуже окрашены

1 2 синий

2 3 синий

3 4 красный

4 1 красный

вывод = 1: потому чтоЕдинственный способ закрасить края покоя, как показано ниже:

1 3 синий

2 4 красный

ограничения:

• 3 <= n<= 100 000 </li>
• ограничение по времени: 1 секунда
• ограничение по памяти: 256 МБ

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

Answer 1

Вот алгоритм линейного времени.

Во-первых, обратите внимание, что каждый цикл допустимой раскраски содержит четное количество красных ребер (я оставлю это в качестве упражнения).Учитывая цвета связующего дерева, существует ровно одно действительное завершение.Уникальность легко доказать, потому что цвет каждого ребра, не входящего в дерево, определяется соотношением цветов ребер дерева, с которым оно образует цикл.Я оставлю валидность в качестве другого упражнения (из-за извинения на время, извините).

Алгоритм состоит в том, чтобы использовать поиск в глубину, чтобы найти остовный лес заданных ребер, сохраняя четность цветов ребер между каждымузел и корень его дерева.Учитывая эти данные, мы можем проверить заданный цвет каждого ребра не в лесу.Если что-то не так, то есть 0 раскрасок.В противном случае существует 2 ^ (количество деревьев минус один) окраски.