Графы. Поиск в глубину. DFS на стеке. Грядки. Немного Монополии. Базовая группа 2022 09 19
3 занятие базовой группы по графам. Получили красивое решение грядок с помощью подсчётов компонент связности, при этом список смежности и массив посещений сделали через контейнер STL map.
В задаче Монополия обсудили идею двудольности для решения.
Моя анкета на профи ру
Ассоциация репетиторов
Мой вк
Группа вк
Задачи взяты с сайта
Грядки
Монополия
0:00 Грядки
18:10 DFS на стеке
43:10 Начало Монополии
Задача №658. Грядки
Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.
Входные данные
В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ N, M ≤ 200.
Выходные данные
Вывести одно число - количество грядок на садовом участке.
Задача №487. Монополия
В Тридесятом государстве есть N фирм, занимающихся разработкой программного обеспечения. Однажды известный олигарх Тридесятого государства Иванушка решил монополизировать эту отрасль. Для этого он хочет купить максимальное число программистских фирм Тридесятого государства.
Он разослал предложения всем N компаниям и через некоторое время получил от каждой их них согласие или отказ. Однако он знает, что в бизнесе очень многое зависит от взаимного доверия партнеров.
В результате небольшого исследования Иванушка установил, между какими компаниями существует взаимное доверие (причем всегда если компания доверяет компании B, то компания B доверяет компании A).
Теперь, при желании, Иванушка может повторно разослать предложения всем компаниям, включив в письма список компаний, давших согласие участвовать в его проекте. При этом каждая компания, независимо от своего первоначального мнения дает согласие, если в списке есть хотя бы одна компания, которой она доверяет, и отказ в противном случае. Таким образом, некоторые компании, которые изначально не согласились участвовать в проекте, могут теперь дать свое согласие, а некоторые из давших согласие — наоборот отказаться. В результате этого у Иванушки формируется новый список, который он опять может разослать фирмам. Он может сколь угодно долго повторять операцию, каждый раз рассылая текущий список. Иванушка может остановить процесс в любой момент и заключить договора с теми, кто после последней рассылки дал согласие.
Напишите программу, которая определит, какое максимальное число компаний может объединить Иванушка под своим началом.
Будем считать, что Иванушка — честный предприниматель и он никогда не подтасовывает рассылаемые им списки.
Входные данные
В первой строке входных данных содержится число N — количество фирм (1≤N≤2000). Далее идут N чисел, описывающих ответ фирмы на первое предложение Иванушки (1 — согласие, 0 — отказ). Далее задается число M (0≤M≤200000) — количество пар компаний, между которыми существует доверие. Далее следуют M пар чисел, задающих номера фирм, между которыми существует взаимное доверие (числа в паре не могут быть одинаковыми). Любая пара компаний упоминается в этом списке не более одного раза.
Выходные данные
Выведите одно число — максимальное число фирм, которое сможет купить Иванушка.
#Графы #Стек #Обход_в_глубину #DFS #informatics #acmp #stepik #олимпиады #РодионСабитов #RodionSabitov #itmo #ИТМО #ВШЭ #Высшая_проба #Ломоносов #ИОИП #Технокубок #МОШ
56 views
4320
1381
3 hours ago 00:19:10 1
В поисках сокровищ Петербурга
5 hours ago 00:10:56 1
Поиск пути наименьшей длины в графе. Алгоритм Дейкстры