138 В деревне 9 домов. Соседними будем считать участки, у которых общий забор. Известно, что у Петра соседи Иван и Антон, Максим и Сергею, Виктор — Дмитрию и Никите, а также по соседству с Никитой, Иван с Сергеем, Евгений с Дмитрием и Серпий больше соседей в деревне нет. Может ли Петр, перелезая через забор, пробраться на участок к Никите?

Привет! Давай попробуем разобраться в этой задаче с соседями. Нам нужно выяснить, есть ли путь от Петра до Никиты, проходя через участки соседей.

Давай построим граф, где дома — это вершины, а соседство — это рёбра (линии).

Известные соседства (рёбра):

• Петр — Иван
• Петр — Антон
• Максим — Сергей
• Виктор — Дмитрий
• Виктор — Никита
• Никита — Иван
• Иван — Сергей
• Евгений — Дмитрий

Теперь поищем путь от Петра до Никиты:

1. Петр -> Иван (у Петра и Ивана есть общий забор)
2. Иван -> Никита (у Ивана и Никиты есть общий забор)

Мы нашли путь! Петр может пойти на участок к Ивану, а от Ивана — на участок к Никите.

Проверим, возможен ли другой путь:

• Петр -> Антон (сосед Петра)
• У Антона больше соседей нет, так что этот путь тупиковый.
• Петр -> Иван -> Сергей (сосед Ивана)
• У Сергея соседи только Максим (и Иван, но мы уже прошли по нему).
• Петр -> Иван -> Никита (сосед Ивана)

Итак, мы нашли путь!

Ответ: Да, Петр может пробраться на участок к Никите. Путь: Петр → Иван → Никита.