Помогите с олимпиадой, пожалуйста...

Задача, которую вам предстоит решить, требует разбиения учеников на группы, основываясь на их способности добираться друг до друга по тропинкам. Мы будем использовать граф для представления домов, где вершины — это дома, а рёбра — это тропинки, по которым дети могут двигаться.

Пошаговое решение

1. Представление города как графа: Каждый дом — это вершина графа. Тропинки между домами — рёбра с весом, который равен расстоянию между домами. Задача сводится к тому, чтобы понять, кто может добраться до кого, при этом не превышая расстояния в 2 единицы.


2. Поиск компонент связности: Мы будем искать компоненты связности в графе, где расстояние между домами не превышает 2 единиц. Для этого можно использовать алгоритм поиска в глубину (DFS) или поиска в ширину (BFS).


3. Разбиение на группы: После того как мы получим компоненты связности, нужно разбить их на группы:

Сначала будем создавать группы по 3 человека (если компонент содержит хотя бы 3 дома).

Оставшихся будем распределять по группам по 2, а те, кто останется, будут одиночками.



4. Алгоритм:

Прочитаем входные данные и создадим граф.

Используем BFS или DFS, чтобы найти компоненты связности для всех домов, между которыми можно пройти, не превышая расстояния в 2 единицы.

Для каждой компоненты вычислим количество одиночек, пар и троек.




Реализация

from collections import deque, defaultdict

def bfs(graph, start, n):
# BFS для поиска всех домов в компоненте связности
queue = deque([start])
visited[start] = True
component = []

while queue:
node = queue.popleft()
component.append(node)
for neighbor, distance in graph[node]:
if not visited[neighbor] and distance <= 2:
visited[neighbor] = True
queue.append(neighbor)

return component

def solve(N, M, roads):
# Строим граф
graph = defaultdict(list)

for road in roads:
u, v, d = road
graph[u].append((v, d))
graph[v].append((u, d))

# Массив для отслеживания посещённых домов
visited = [False] * (N + 1)

# Список для хранения всех компонент связности
components = []

for i in range(1, N + 1):
if not visited[i]:
component = bfs(graph, i, N)
components.append(component)

# Подсчитаем количество одиночек, пар и троек
single = 0
pairs = 0
triples = 0

for component in components:
size = len(component)
triples += size // 3
size %= 3
pairs += size // 2
size %= 2
single += size

return single, pairs, triples

# Чтение входных данных
N, M = map(int, input().split())
roads = [tuple(map(int, input().split())) for _ in range(M)]

# Решение задачи
single, pairs, triples = solve(N, M, roads)

# Вывод результата
print(single)
print(pairs)
print(triples)

Пояснение:

1. Граф:

Используем словарь graph, где ключи — это номера домов, а значения — это списки соседей с расстояниями.



2. Поиск компонент связности:

Используем BFS для поиска всех домов в компоненте связности. В процессе обхода учитываем, что расстояние между домами не должно превышать 2 единицы.



3. Распределение учеников по группам:

После нахождения компонент вычисляем, сколько учеников может быть в каждой группе (по 3, по 2 и по 1).



4. Чтение и обработка входных данных:

Считываем данные с входа и передаем в функцию solve, которая решает задачу.




Пример

Входные данные:

15 4
1 2 1
2 3 2
4 5 1
4 2 3

Выходные данные:

0
1
1

Входные данные:

110 9
1 3 2
3 2 1
3 4 1
5 6 1
7 5 2
7 6 1
9 6 3
9 8 1
7 8 2

Выходные данные:

1
3
1