Тимур — поставщик продуктов в рестораны. Всего есть n ресторанов, в c из которых Тимур…
- User
Тимур — поставщик продуктов в рестораны. Всего есть n ресторанов, в c из которых Тимур уже поставляет продукты. Также m пар ресторанов являются соседями друг для друга, при этом ресторан не может быть соседом сам себе и никакие два ресторана не могут быть соседями дважды. Ресторан нанимает Тимура как поставщика, если хотя бы в k соседей этого ресторана Тимур уже поставляет продукты. Напиши программу на java, которая узнает, сколько ресторанов наймут его по итогу.
Формат входных данных Первая строка содержит три целых числа n, m, k (1 =< k =< n =< 2·10^5, 1 =< m =< 2·10^5), обозначающие количество ресторанов, количество пар соседей и количество соседей, необходимое для того, чтобы ресторан нанял Тимура, соответственно. В следующих m строчках содержится описание пар соседних ресторанов. Каждая строка содержит два различных целых числа — номера двух ресторанов, соседних друг другу. В следующей строке содержится целое число c (0 =< c =< n), обозначающее количество ресторанов, в которые Тимур с самого начала поставляет продукты. В следующей строке содержится c различных целых чисел от 1 до n — номера ресторанов, в которые Тимур уже поставляет продукты.
Формат выходных данных В первой строке выведите целое число a — количество ресторанов, которые однажды наймут Тимура как поставщика. Во второй строке выведите a целых чисел — номера всех ресторанов, в которые Тимур будет поставлять продукты, в любом порядке.
- Assistant
В данной задаче можно использовать алгоритм обхода графа, так как рестораны и их соседи образуют граф.
Алгоритм решения задачи:
- Создать массив размером n, в котором будем хранить информацию о том, поставляет ли Тимур продукты в данный ресторан.
- Пройтись по списку ресторанов, в которые Тимур уже поставляет продукты, и пометить соответствующие элементы массива как true (Тимур уже поставляет продукты в эти рестораны).
- Пройтись по списку пар соседних ресторанов и пометить элементы массива соответствующих ресторанов как true, если соседний ресторан уже помечен как true и имеет необходимое количество соседей, получающих продукты от Тимура.
- Подсчитать количество ресторанов, в которые Тимур будет поставлять продукты, и создать новый массив для их хранения.
- Пройтись по массиву и записать номера ресторанов, в которые Тимур будет поставлять продукты, в новый массив.
- Вывести количество ресторанов и список номеров ресторанов, в которые Тимур будет поставлять продукты.
Пример реализации на Java:
import java.util.*;
public class TimurRestaurant { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int k = scanner.nextInt();
List<Integer>[] neighbors = new ArrayList[n+1]; // массив списков соседей для каждого ресторана for (int i = 1; i <= n; i++) { neighbors[i] = new ArrayList<>(); } for (int i = 0; i < m; i++) { int a = scanner.nextInt(); int b = scanner.nextInt(); neighbors[a].add(b); neighbors[b].add(a); } int c = scanner.nextInt(); boolean[] isSupplier = new boolean[n+1]; // массив для хранения информации о том, поставляет ли Тимур продукты в данный ресторан for (int i = 0; i < c; i++) { int restaurant = scanner.nextInt(); isSupplier[restaurant] = true; } for (int i = 1; i <= n; i++) { if (isSupplier[i]) { // если Тимур уже поставляет продукты в данный ресторан for (int neighbor : neighbors[i]) { if (!isSupplier[neighbor]) { // если соседний ресторан еще не помечен как true int neighborsWithSupplier = 0; // количество соседей, получающих продукты от Тимура for (int nighborNeighbor : neighbors[neighbor]) { if (isSupplier[nighborNeighbor]) { neighborsWithSupplier++; } } if (neighborsWithSupplier >= k) { isSupplier[neighbor] = true; // помечаем ресторан как тот, в котором Тимур будет поставлять продукты } } } } } int supplierCount = 0; // количество ресторанов, в которые Тимур будет поставлять продукты List<Integer> supplierRestaurants = new ArrayList<>(); // список ресторанов, в которые Тимур будет поставлять продукты for (int i = 1; i <= n; i++) { if (isSupplier[i]) { supplierCount++; supplierRestaurants.add(i); } } System.out.println(supplierCount); for (int restaurant : supplierRestaurants) { System.out.print(restaurant + " "); } }}