N. Сколько компонент — деревья
3000 мс · 256 МБ · всё или ничего
Неориентированный граф задан списком рёбер. Посчитайте, сколько компонент связности являются деревьями.
Компонента — дерево, если в ней рёбер ровно на одно меньше, чем вершин. Считать рёбра компоненты надо аккуратно: каждое ребро принадлежит ровно одной компоненте, петли и кратные рёбра тоже считаются.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рёбрами. Возможны петли и кратные рёбра.
Формат вывода
Одно число — количество компонент, являющихся деревьями.
Примеры
ввод
5 3 1 2 2 3 4 5
вывод
2
ввод
6 4 1 2 2 3 3 1 4 5
вывод
2
Войдите, чтобы отправлять решения.