Здравствуйте, Кодт, Вы писали:
К>https://www.hackerrank.com/challenges/even-tree
К>Дано: дерево (связный ациклический граф) из N вершин.
К>Найти максимальное количество рёбер, которые следует удалить, чтобы в получившемся лесу все деревья состояли из чётного числа вершинкоторое можно удалить так, что в получившемся лесу все деревья состоят из чётного числа вершин.
Fixed.
К>Вход: количество вершин N, количество рёбер M, и далее список из M рёбер в виде пар вершин (где вершины пронумерованы от 1 до N)
К>Выход: количество удалённых рёбер
Вроде все просто.
Если N нечетное, то ответ 0.
Иначе, считаем числа вершин в поддеревьях (рекурсивно от корня к листьям). Как только набираем "четное" поддерево, отрезаем его, увеличивая результат.
Сложность — O(N).