Данил268905
14.10.2021 10:16

A. Лес Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Дан лес. Найдите количество деревьев в нём.

Гарантируется, что во входных данных лес.

Примечание: Лес — это множество деревьев. Дерево — это связный ациклический граф. Будем считать, что граф, состоящий из одной изолированной вершины, тоже является деревом.

Формат ввода
В первой строке даны два целых числа n (1 ≤ n ≤ 105) и m(0 ≤ m ≤ n-1) - число вершин и ребер соответственно.

В последующих m строках даны два целых числа u и v(1 ≤ u,v ≤ n, ) - две вершины между которыми есть ребро.

Формат вывода
Выведите одно число — количество деревьев в лесу.

Пример
Ввод Вывод
7 4
1 2
3 2
4 5
5 6
3

Нажмите на рекламу ниже и сразу увидите ответ
Популярные вопросы:
Ответ:
JustTonight
05.01.2022 21:35

но у меня извиняйте ,как могу

Объяснение:

n,m=map(int,input().split())

tree=[]

count_tree=0

for i in range(m):

   u,v = map(int,input().split())

   not_in_tree = True

   for tr in tree:

       if u in tr:

           if v not in tr:

               tr.append(v)

               count_tree +=1

               not_in_tree=False

               break

       elif v in tr:

           if u not in tr:

               tr.append(u)

               count_tree +=1

               not_in_tree=False

               break

   if not_in_tree:

       tree.append([u,v])

       count_tree +=2

print(len(tree) + (n-count_tree))

0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота