Необходимо произвести деталь номер 1. Определите, какое наименьшее число деталей (суммарно, включая саму деталь номер 1) нужно произвести для этого, с учетом всех необходимых зависимостей.
ВХОДНЫЕ ДАННЫЕ
Первая строка входных данных содержит число n, (1≤n≤100000). Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит список деталей, которые требуются для производства детали с номером i. В списке нет повторяющихся номеров деталей. Список может быть пустым: тогда ему будет соответствовать пустая строка!
Суммарно во всех списках содержится не более 200000 элементов. Гарантируется, что не существует циклических зависимостей в производстве деталей.
ВЫХОДНЫЕ ДАННЫЕ
Программа должна вывести одно натуральное число — минимальное количество деталей, которые должен произвести завод для производства детали номер 1.
ПРИМЕР
ввод
3
2
1 2
вывод
2
комментарий
Для производства детали номер 1 нужна деталь номер 2, для производства детали номер 2 ничего не нужно, поэтому нужно произвести 2 детали.
ввод
6
3 6
4
2 6
4
вывод
4
комментарий
Для производства детали 1 нужны детали 3 и 6, каждая из них требует для производства деталь 4. Итого нужно произвести 4 детали (1, 3, 6, 4), детали 2 и 5 производить не нужно.
Для решения этой задачи, мы можем использовать алгоритм топологической сортировки. Этот алгоритм позволяет упорядочить вершины в графе таким образом, чтобы каждое ребро было направлено от вершины с меньшим номером к вершине с большим номером.
В данной задаче, граф представляет собой зависимости между деталями. Если деталь A требуется для производства детали B, то мы можем добавить ребро из вершины A в вершину B в графе.
Алгоритм топологической сортировки будет итеративно проходить по вершинам графа, начиная с детали номер 1, и подсчитывать минимальное количество деталей, которые необходимо произвести для производства детали номер 1.
Вот решение задачи на Python, используя алгоритм топологической сортировки:
from collections import deque
def min_parts(n, dependencies):
# Создаем граф зависимостей
graph = [[] for _ in range(n+1)]
for i in range(1, n+1):
for dep in dependencies[i]:
graph[dep].append(i)
# Инициализируем массив для хранения количества деталей
parts_count = [0] * (n+1)
# Очередь для обхода вершин в графе
queue = deque()
queue.append(1) # Начинаем с детали номер 1
# Итеративно обходим вершины графа
while queue:
part = queue.popleft()
for dep in graph[part]:
parts_count[dep] = max(parts_count[dep], parts_count[part] + 1)
queue.append(dep)
# Находим максимальное количество деталей
max_count = max(parts_count)
# Возвращаем минимальное количество деталей для производства детали номер 1
return max_count + 1
# Считываем входные данные
n = int(input())
dependencies = {}
for i in range(1, n+1):
dependencies[i] = list(map(int, input().split()))
# Вызываем функцию и выводим результат
result = min_parts(n, dependencies)
print(result)
В этом коде мы сначала создаем граф зависимостей, используя входные данные. Затем мы инициализируем массив parts_count для хранения количества деталей, и очередь queue для обхода вершин в графе.
Затем мы начинаем итеративно обходить вершины графа, начиная с детали номер 1. Для каждой вершины мы проверяем все ее зависимости и обновляем количество деталей, необходимых для их производства. Мы также добавляем зависимые детали в очередь для дальнейшего обхода.
В конце мы находим максимальное количество деталей в массиве parts_count и возвращаем это значение, увеличенное на 1, так как входная деталь (номер 1) также должна быть произведена.
Пример реализации 2:
def parts(n=0):
nl.add(str(n + 1))
if ml[n]:
for i in ml[n]:
parts(int(i)-1)
return len(nl)
n = int(input())
ml = [input().split() for _ in range(n)]
nl = set()
print(parts())