Помните задачку из классной работы про транспортную сеть между планетами Солнечной системы (и Плутоном)? Так вот, за время, пока Вы добирались до домашки, она успела разрастись на…
Помните задачку из классной работы про транспортную сеть между планетами Солнечной системы (и Плутоном)? Так вот, за время, пока Вы добирались до домашки, она успела разрастись на всю Вселенную! Теперь она выглядит следующим образом: Из Млечного Пути можно добраться до Черной дыры Из Черной дыры можно попасть в центр Вселенной Из Андромеды можно попасть в Млечный Путь, Черную дыру, центр Вселенной, Большую медведицу, Альфа Центавру Из центра Вселенной можно попасть в Большую Медведицу из Большой медведицы можно попасть в Альфа Центавру Из Альфа Центавры можно попасть в Сириус и центр Вселенной Из Сириуса можно попасть в Млечный Путь, Черную дыру, Андромеду и центр Вселенной
Классная задача превращается в графовую: вершины — локации,DirectedEdges — пути между ними. Ниже решение с понятными шагами.
- Вершины (узлы графа)
- Млечный Путь (MW)
- Черная дыра (BH)
- Центр Вселенной (CU)
- Андромеда (AN)
- Большая Медведица (UMA)
- Альфа Центавра (AC)
- Сириус (SI)
- Плутон (PL) — упомянут в вводной, но в списке ребер его не видно. Мы учтем, что PL — изолированная вершина (нет входов и выходов), если не указано иное.
- Ребра (направленные пути)
- MW -> BH
- BH -> CU
- AN -> MW
- AN -> BH
- AN -> CU
- AN -> UMA
- AN -> AC
- CU -> UMA
- UMA -> AC
- AC -> SI
- AC -> CU
- SI -> MW
- SI -> BH
- SI -> AN
- SI -> CU
- Что можно заметить по графу
- Есть очень ярко выраженный цикл, переходящий через все узлы: AN -> MW -> BH -> CU -> UMA -> AC -> SI -> AN. Это значит, что последовательно проходя по этим рёбрам, можно добраться от любой локации к любой другой через этот цикл.
- Следовательно, для узлов MW, BH, CU, AN, UMA, AC, SI существует взаимная достижимость: из любого из них можно добраться до любого другого(otherwise путь можно подобрать по циклу выше).
- Плутон PL в этом списке не участвует в рёбрах. Значит PL — изолированная вершина: из неё никуда не попасть и к ней никто не попасть не может, если специально не добавлять рёбра. Это отдельно стоит отметить.
- Вывод по задаче
- За счёт Hamilton-подобного цикла AN -> MW -> BH -> CU -> UMA -> AC -> SI -> AN вся сеть взаимно достижима между 7 узлами: можно добраться из любой локации в любую другую.
- Плутон не входит в этот цикл и в текущем списке ребер остается изолированной точкой (если не добавить дополнительных ребер).
- Примеры путей (для конкретной пары)
- Из Андромеды в Сириус: AN -> AC -> SI (прямой путь по цепочке AN -> AC, AC -> SI).
- Из Сириуса в Андромеду: SI -> AN (прямой путь).
- Из Млечного Пути в Центр Вселенной: MW -> BH -> CU.
- Из Андромеды в Млечный Путь: AN -> MW (прямой путь).
- Из Андромеды в Большую Медведицу: AN -> UMA (прямой путь).
- Из Сириуса в Андромеду через цикл: SI -> AN.
- Если ввести Плутон PL как отдельную вершину, то из него пути не выходят (и к нему не ведут) без добавления новых рёбер.
- Быстрый способ проверки (для учёбы)
- Заметим cycle: AN -> MW -> BH -> CU -> UMA -> AC -> SI -> AN.
- Так как этот цикл покрывает все перечисленные узлы, они образуют одну сильно связную компоненту: From any node you can добраться до любого другого узла того же набора.
- Дополнительно (для подготовки к задачам)
- Можно посчитать матрицу достижимости или выполнить обходы DFS/BFS для каждой вершины, чтобы явно увидеть, что все пары достижимы.
- Если нужно привести решение в коде, можно привести простой пример на Python с использованием BFS для каждой вершины, либо применить Floyd-Warshall для транспитивной замкнутости graph.
Пример небольшого кода (псевдокод на Python) для транспитивной замкнутости:
- создать словарь adjacency с рёбрами
- для каждой вершины выполнить DFS/BFS и собрать достижимые вершины
- вывести множество достижимых для каждой вершины
Итого: для данной задачи с данными рёбрами сеть между MW, BH, CU, AN, UMA, AC и SI полностью взаимно достижима. Плутон остаётся изолированной точкой, если явным образом не добавить к нему рёбра. Это отличный пример того, как из простого цикла можно получить полноценную взаимную доступность в графе.
