Guest
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 #ИТМО #ВШЭ #Высшая_проба #Ломоносов #ИОИП #Технокубок #МОШ
