Где применяется
1. Задача
В прошлой группе уроков ты работал с деревьями: корень, под ним дети, и до любого узла ведёт один понятный путь вниз. Дерево (tree) это граф без циклов, в котором между любыми двумя узлами ровно один путь. Обычный граф (graph) не обещает ни того, ни другого. Связи могут замыкаться в круг, а между двумя узлами может быть много путей или ни одного.
Графом описывается почти всё в жизни: города и дороги между ними, люди и подписки друг на друга, веб-страницы, которые ссылаются друг на друга по кругу, задачи, которые ждут других задач. Ничто из этого не укладывается в дерево, где связи идут только сверху вниз.
Прежде чем обходить граф, искать кратчайший путь или считать его части, граф надо сохранить в памяти. Этот урок только об этом: как хранить узлы и связи, чтобы следующим алгоритмам было что читать.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на граф, где ответ следует из того, кто с кем связан, например из степеней и прямых связей. Один раз построй список смежности и считай входящие и исходящие рёбра, когда они нужны.
Центр это узел со степенью n минус 1, и он общий у первых двух рёбер.
Посчитай входящие и исходящие рёбра, у судьи n минус 1 входящих и 0 исходящих.
Складывай степени каждой пары городов и вычитай 1, если они связаны напрямую, а это за O(1) скажет множество рёбер.
Ответ это все узлы без входящих рёбер, потому что до них не дойти ниоткуда.