Брутфорс Временная Сложность Четного Дерева
Я работаю над проблемой: https://www.hackerrank.com/challenges/even-tree.
У меня есть решение, которое по своей природе является грубым. Я хотел проверить, является ли это правильным грубым временным усложнением этой проблемы. Если да, то я могу думать о том, как я могу сделать лучше.
Алгоритм
- Получить все подмножества ребер данного графа (я получаю все комбинации ребер, чтобы потом их можно было удалить из графа). -> О (2PowerE)
- Начните с максимального размера подмножества. Для каждого подмножества удалите все эти ребра из графика. Запустите DFS, чтобы выяснить, имеют ли оставшиеся отключенные компоненты четное число узлов. -> O(V+E)
- Прерывание итераций, когда определенное удаление ребер приводит к лесу с каждым отключенным компонентом, имеющим четное число узлов.
Сложность вышеуказанного решения O(2PowerE*(V + E)). Дайте мне знать, если это решение работает и квалифицируется как грубая сила.