Какое свойство графа нужно задаче?

У графа разные вопросы: встретиться на середине пути, разделить конфликтующие вершины на две группы, свернуть взаимные зависимости, найти хрупкие связи, пройти каждое ребро, отвечать о предках или перевезти максимум материала.

Каждому вопросу нужен свой инвариант. Один массив посещённости не различает активного предка DFS, завершённое поддерево, использованное ребро и оставшуюся транспортную пропускную способность.

Сначала изучи BFS, DFS с кадрами, деревья и смежность. Вершины — целые 0 until V. Неориентированные примеры принимают один UEdge на логическое ребро и сами создают два направления. Параллельные рёбра и петли сохраняют отдельные идентификаторы. У ориентированных алгоритмов свои типы рёбер.

Идея: сохранить забытое обычной достижимостью

Двунаправленный BFS хранит слои расстояний от обоих концов. Проверка двудольности — сторону назначенного цвета. Сильным компонентам нужны взаимная направленная достижимость и доказательство порядка завершения, а не обычные неориентированные компоненты.

Для неориентированного DFS entered[v] — время обнаружения. low[v] — самое раннее обнаружение, достижимое из поддерева v спуском по рёбрам дерева и не больше чем одним обратным ребром вверх, включая саму v. Значение ребёнка показывает, может ли поддерево соединиться выше родителя.

Эйлеров обход помечает логические рёбра: вершины могут повторяться. Двоичный подъём хранит предков на расстояниях степеней двойки. Максимальный поток хранит остаточную пропускную способность: свободный прямой ресурс и возможность отменить прежнюю маршрутизацию.

Это разные смыслы состояния. Подходящая структура с неправильным смыслом состояния всё равно даёт неправильный алгоритм.

Главное, что нужно запомнить

Сначала направление и модель: неориентированная связность, направленная взаимная достижимость и дерево с корнем — разные контракты.
Выбери считаемый объект: кратчайший путь считает рёбра, эйлеров использует рёбра, гамильтонов тур посещает вершины.
Сохраняй идентичность ребра: при параллельных рёбрах пропускается конкретное родительское, а не все связи с родителем.
Учитывай завершение: порядок SCC и передача low-link требуют готового состояния детей.
Докажи остановку: встреча слоёв, исчерпание рёбер и отсутствие остаточного увеличивающего пути имеют разные доказательства.

Массивы смежности строятся внутри примеров, доступ к вершине по индексу — O(1). Обходы используют явные стеки или очереди вместо рекурсии. Формулы расстояний имеют промежуточный Long, ёмкости — проверяемую арифметику Long. Допустимый вход всё ещё должен помещаться в доступную память.

Сравни разные вопросы на одном графе

неориентированный граф:
0 --- 1 --- 3 --- 4
 \   /
   2

мосты: 1--3 и 3--4
точки сочленения: 1 и 3
не двудольный: треугольник 0,1,2 — нечётный цикл
эйлеров путь есть: 1,0,2,1,3,4

ориентированный граф:
0 -> 1 -> 2 -> 0; 2 -> 3; 3 <-> 4
сильные компоненты: {0,1,2} -> {3,4}

поток u -> v, ёмкость 3, увеличение на 2:
прямой остаток 1; обратная возможность отмены 2

Треугольник мешает двум цветам, но не эйлерову пути. Конец моста не обязательно является точкой сочленения: лист таким не является. Предсказывай свойства по определениям, а не кажущейся сложности рисунка.

Разборы: границы поиска, группы, предки и рёбра

Двудольность двумя цветами

bipartiteColors(V,edges) возвращает цвета 0/1 всех вершин либо null, если ребро нельзя соединить противоположными цветами. Пустой вход даёт пустой массив. Петля запрещает двудольность, параллельные рёбра не меняют возможность. Каждая несвязная компонента начинает собственный BFS.

data class UEdge(val first: Int, val second: Int)
private data class Arc(val to: Int, val edge: Int)

private fun undirectedAdjacency(vertices: Int, edges: List<UEdge>): Array<MutableList<Arc>> {
    require(vertices >= 0)
    val graph = Array(vertices) { mutableListOf<Arc>() }
    edges.forEachIndexed { index, edge ->
        require(edge.first in graph.indices && edge.second in graph.indices)
        graph[edge.first].add(Arc(edge.second, index))
        graph[edge.second].add(Arc(edge.first, index))
    }
    return graph
}

fun bipartiteColors(vertices: Int, edges: List<UEdge>): IntArray? {
    val graph = undirectedAdjacency(vertices, edges)
    val color = IntArray(vertices) { -1 }
    val queue = ArrayDeque<Int>()
    for (start in graph.indices) {
        if (color[start] != -1) continue
        color[start] = 0
        queue.addLast(start)
        while (queue.isNotEmpty()) {
            val vertex = queue.removeFirst()
            for ((next, _) in graph[vertex]) {
                if (color[next] == -1) {
                    color[next] = 1 - color[vertex]
                    queue.addLast(next)
                } else if (color[next] == color[vertex]) return null
            }
        }
    }
    return color
}

Каждый новый сосед получает противоположный цвет. Ребро одинаковых цветов противоречит инварианту и свидетельствует о нечётном цикле. Обратно, противоположные цвета всех концов образуют допустимое разбиение. Время и общая дополнительная память — O(V+E) со смежностью; цвета результата занимают O(V).

Двунаправленный BFS

bidirectionalDistance возвращает минимальное число рёбер между корректными концами неориентированного графа либо null при несвязности. Одинаковые концы дают ноль. Стороны хранят полные слои; целиком раскрывай меньший текущий слой и проверяй встречи с посещённой областью другой стороны.

fun bidirectionalDistance(vertices: Int, edges: List<UEdge>, start: Int, goal: Int): Int? {
    val graph = undirectedAdjacency(vertices, edges)
    require(start in graph.indices && goal in graph.indices)
    if (start == goal) return 0
    val leftDistance = IntArray(vertices) { -1 }
    val rightDistance = IntArray(vertices) { -1 }
    leftDistance[start] = 0; rightDistance[goal] = 0
    var left = listOf(start)
    var right = listOf(goal)
    fun expand(frontier: List<Int>, own: IntArray, other: IntArray): Pair<List<Int>, Int?> {
        val nextLayer = mutableListOf<Int>()
        var best: Long? = null
        for (vertex in frontier) for ((next, _) in graph[vertex]) {
            if (own[next] != -1) continue
            own[next] = own[vertex] + 1
            nextLayer.add(next)
            if (other[next] != -1) {
                val candidate = own[next].toLong() + other[next]
                best = best?.let { minOf(it, candidate) } ?: candidate
            }
        }
        return nextLayer to best?.let { Math.toIntExact(it) }
    }
    while (left.isNotEmpty() && right.isNotEmpty()) {
        if (left.size <= right.size) {
            val (next, answer) = expand(left, leftDistance, rightDistance)
            if (answer != null) return answer
            left = next
        } else {
            val (next, answer) = expand(right, rightDistance, leftDistance)
            if (answer != null) return answer
            right = next
        }
    }
    return null
}

До встречи исследованные шары расстояний не пересекаются. Раскрытие одного полного следующего слоя находит первую возможную суммарную глубину; минимум встреч внутри слоя безопасен. Переключение после произвольных отдельных вершин потребовало бы другого доказательства остановки.

Общая оценка остаётся O(V+E) времени и памяти с построением. В древовидных графах со сбалансированным ветвлением поиск видит существенно меньше вершин, но приближение b^(d/2) не является универсальной гарантией графов. Направленному обратному поиску нужны обратные рёбра; эта функция неориентированная.

Сильные компоненты алгоритмом Косарайю

stronglyConnectedComponents(V, directedEdges) возвращает метку каждой вершины и число компонент. У меток нет прикладного смысла; равенство означает взаимную достижимость. Допустимы петли, параллельные рёбра, изолированные вершины и пустой граф.

data class DirectedEdge(val from: Int, val to: Int)
data class SccResult(val component: IntArray, val count: Int)

fun stronglyConnectedComponents(vertices: Int, edges: List<DirectedEdge>): SccResult {
    require(vertices >= 0)
    val graph = Array(vertices) { mutableListOf<Int>() }
    val reversed = Array(vertices) { mutableListOf<Int>() }
    for ((from, to) in edges) {
        require(from in graph.indices && to in graph.indices)
        graph[from].add(to); reversed[to].add(from)
    }
    data class Frame(val vertex: Int, var next: Int = 0)
    val visited = BooleanArray(vertices)
    val frames = ArrayDeque<Frame>()
    val finished = mutableListOf<Int>()
    for (start in graph.indices) {
        if (visited[start]) continue
        visited[start] = true; frames.addLast(Frame(start))
        while (frames.isNotEmpty()) {
            val frame = frames.last()
            if (frame.next == graph[frame.vertex].size) {
                frames.removeLast(); finished.add(frame.vertex)
            } else {
                val next = graph[frame.vertex][frame.next++]
                if (!visited[next]) { visited[next] = true; frames.addLast(Frame(next)) }
            }
        }
    }
    val component = IntArray(vertices) { -1 }
    val stack = ArrayDeque<Int>()
    var count = 0
    for (start in finished.asReversed()) {
        if (component[start] != -1) continue
        component[start] = count; stack.addLast(start)
        while (stack.isNotEmpty()) {
            val vertex = stack.removeLast()
            for (next in reversed[vertex]) if (component[next] == -1) {
                component[next] = count; stack.addLast(next)
            }
        }
        count++
    }
    return SccResult(component, count)
}

Первый проход пишет настоящий порядок завершения DFS кадрами с позицией следующего соседа. Второй обходит обратный граф по убыванию времени завершения. Конденсация ациклична; порядок не позволяет поглотить другую ещё не назначенную компоненту. Поэтому один второй обход помечает ровно одну SCC.

Время и память — O(V+E), включая транспонирование и кадры. Тарьян — другой линейный вариант: индексы обнаружения, low-link и отдельный стек активных вершин в одном DFS. Здесь реализован Косарайю; правила мостов неориентированного графа не заменяют правила активного стека Тарьяна.

Общие предки двоичным подъёмом

BinaryLiftingLca(V,edges,root) требует непустое неориентированное дерево и корректный фиксированный корень. Конструктор отклоняет неправильные концы, петли, параллельные рёбра, циклы и несвязность. lca(a,b) возвращает самого глубокого общего предка, включая сами аргументы. distance считает рёбра дерева как Long.

class BinaryLiftingLca(vertices: Int, edges: List<UEdge>, root: Int = 0) {
    private val depth: IntArray
    private val up: Array<IntArray>

    init {
        val graph = undirectedAdjacency(vertices, edges)
        require(root in graph.indices && edges.size == vertices - 1)
        depth = IntArray(vertices)
        val parent = IntArray(vertices) { -1 }
        val parentEdge = IntArray(vertices) { -1 }
        val queue = ArrayDeque<Int>()
        parent[root] = root; queue.addLast(root)
        var visited = 0
        while (queue.isNotEmpty()) {
            val vertex = queue.removeFirst(); visited++
            for ((next, edge) in graph[vertex]) {
                if (edge == parentEdge[vertex]) continue
                require(parent[next] == -1) { "edges must form a tree" }
                parent[next] = vertex; parentEdge[next] = edge
                depth[next] = depth[vertex] + 1
                queue.addLast(next)
            }
        }
        require(visited == vertices) { "tree must be connected" }
        var levels = 1
        while ((1L shl levels) <= vertices.toLong()) levels++
        up = Array(levels) { IntArray(vertices) }
        up[0] = parent
        for (level in 1 until levels) for (vertex in graph.indices) {
            up[level][vertex] = up[level - 1][up[level - 1][vertex]]
        }
    }

    fun lca(first: Int, second: Int): Int {
        require(first in depth.indices && second in depth.indices)
        var a = first; var b = second
        if (depth[a] < depth[b]) { val swap = a; a = b; b = swap }
        val difference = depth[a] - depth[b]
        for (level in up.indices) if ((difference and (1 shl level)) != 0) a = up[level][a]
        if (a == b) return a
        for (level in up.indices.reversed()) if (up[level][a] != up[level][b]) {
            a = up[level][a]; b = up[level][b]
        }
        return up[0][a]
    }

    fun distance(first: Int, second: Int): Long {
        val ancestor = lca(first, second)
        return depth[first].toLong() + depth[second] - 2L * depth[ancestor]
    }
}

up[k][v] — предок на расстоянии 2^k; корень — собственный предок. Сначала подними более глубокую вершину до одинаковой глубины. Затем пробуй убывающие прыжки, двигая обе вершины только при разных предлагаемых предках. Они остановятся прямо под ближайшим общим предком.

Подготовка и память — O(V log(V+1)), запрос — O(log(V+1)). Формула расстояния: depth[a]+depth[b]-2*depth[lca] с промежуточным Long. Изменение дерева или корня требует пересоздать этот статический индекс.

Каждое ребро один раз алгоритмом Хиерхольцера

eulerTrail(V,edges) возвращает маршрут вершин с каждым неориентированным ребром ровно один раз либо null. Вершины могут повторяться; изолированные появляться не обязаны. Без рёбер верни [0] при V>0 и пустой маршрут при V=0.

fun eulerTrail(vertices: Int, edges: List<UEdge>): List<Int>? {
    val graph = undirectedAdjacency(vertices, edges)
    if (edges.isEmpty()) return if (vertices == 0) emptyList() else listOf(0)
    val odd = graph.indices.filter { graph[it].size % 2 == 1 }
    if (odd.size != 0 && odd.size != 2) return null
    val start = odd.firstOrNull() ?: graph.indices.first { graph[it].isNotEmpty() }
    val next = IntArray(vertices)
    val used = BooleanArray(edges.size)
    val stack = ArrayDeque<Int>()
    val reversed = mutableListOf<Int>()
    stack.addLast(start)
    while (stack.isNotEmpty()) {
        val vertex = stack.last()
        while (next[vertex] < graph[vertex].size && used[graph[vertex][next[vertex]].edge]) next[vertex]++
        if (next[vertex] == graph[vertex].size) reversed.add(stack.removeLast())
        else {
            val arc = graph[vertex][next[vertex]++]
            used[arc.edge] = true
            stack.addLast(arc.to)
        }
    }
    if (reversed.size.toLong() != edges.size.toLong() + 1) return null
    reversed.reverse()
    return reversed
}

Непустому эйлерову пути нужны ноль или две нечётные степени и связность вершин с рёбрами. Начни с нечётной, если она есть. Иди по неиспользованным рёбрам, затем записывай вершины без продолжений. Разворот порядка завершения неявно сшивает циклы.

Идентификаторы не дают использовать петлю или параллельное ребро дважды. Проверка итоговой длины отклоняет несвязные компоненты с рёбрами. Время — O(V+E), рабочая память — O(V+E), результат — O(E+1). Это обход рёбер, а не гамильтонов тур вершин.

Где контракты перестают подходить

Общий предок дерева не переносится напрямую на ориентированный граф с несколькими несравнимыми общими предками. Два цвета не решают произвольную многоцветную раскраску. Критерии неориентированных мостов не находят направленные сильные мосты.

Возврат меток или числа не выдаёт свидетельство автоматически. Отказ двудольности здесь не возвращает нечётный цикл, а максимальный поток ниже — назначения по рёбрам. Такой вывод нужно добавить явно.

Двунаправленный поиск и двоичный подъём оптимизируют конкретную повторяемую работу. Для одного маленького запроса обычный BFS или подъём по родителям бывает проще реализовать и проверить.

Частые ошибки

Пропускать все рёбра к родителю и ошибочно считать параллельные мостами.
Использовать одинаковое строгое сравнение для мостов и точек сочленения.
Применять правило обычной вершины к корню DFS.
Записывать порядок обнаружения вместо завершения для Косарайю.
Проверять степени Эйлера, забывая несвязные компоненты с рёбрами.
Не добавлять обратный остаток и терять возможность перемаршрутизировать поток.
Менять дерево и сохранять старую таблицу подъёма.

Практика: сначала попробуй самостоятельно

Задача 1: мосты и точки сочленения

Реализуй bridgesAndCuts(V,edges): LowLinkResult для возможно несвязного неориентированного мультиграфа. Верни входные индексы мостов по возрастанию и Boolean-флаг точки сочленения каждой вершины. Удаление моста увеличивает число компонент; удаление точки увеличивает число компонент оставшихся вершин.

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

Подсказка 1

Для ребёнка c вершины v сравни low[c] и entered[v]. Возврат в саму v спасает ребро, но не связность после удаления v.

Подсказка 2

Ребро — мост при low[c] > entered[v]. Некорневая v — точка при low[c] >= entered[v] хотя бы одного ребёнка. Корню нужно больше одного ребёнка DFS. Передавай low ребёнка только при завершении его кадра.

Решение и объяснение

Low больше времени родителя означает отсутствие альтернативной связи через границу поддерева. Равенство позволяет вернуться к родителю и спасает ребро, но не даёт выхода после удаления родителя. У корня нет предка; отдельный критерий — число независимых детей DFS.

data class LowLinkResult(val bridges: List<Int>, val articulation: BooleanArray)

fun bridgesAndCuts(vertices: Int, edges: List<UEdge>): LowLinkResult {
    val graph = undirectedAdjacency(vertices, edges)
    data class Frame(val vertex: Int, val parent: Int, val parentEdge: Int, var next: Int = 0, var children: Int = 0)
    val entered = IntArray(vertices) { -1 }
    val low = IntArray(vertices)
    val bridge = BooleanArray(edges.size)
    val cut = BooleanArray(vertices)
    val stack = ArrayDeque<Frame>()
    var clock = 0
    for (root in graph.indices) {
        if (entered[root] != -1) continue
        entered[root] = clock++; low[root] = entered[root]
        stack.addLast(Frame(root, -1, -1))
        while (stack.isNotEmpty()) {
            val frame = stack.last()
            if (frame.next < graph[frame.vertex].size) {
                val arc = graph[frame.vertex][frame.next++]
                if (arc.edge == frame.parentEdge) continue
                if (entered[arc.to] == -1) {
                    frame.children++
                    entered[arc.to] = clock++; low[arc.to] = entered[arc.to]
                    stack.addLast(Frame(arc.to, frame.vertex, arc.edge))
                } else low[frame.vertex] = minOf(low[frame.vertex], entered[arc.to])
            } else {
                stack.removeLast()
                if (frame.parent == -1) cut[frame.vertex] = frame.children > 1
                else {
                    low[frame.parent] = minOf(low[frame.parent], low[frame.vertex])
                    if (low[frame.vertex] > entered[frame.parent]) bridge[frame.parentEdge] = true
                    if (stack.last().parent != -1 && low[frame.vertex] >= entered[frame.parent]) cut[frame.parent] = true
                }
            }
        }
    }
    return LowLinkResult(edges.indices.filter { bridge[it] }, cut)
}

Используются UEdge, Arc и построение смежности. Пропускай точный идентификатор родительского ребра: второе параллельное является допустимой обратной связью. Кадр хранит позицию следующего соседа и число детей.

Время и память — O(V+E); один проход по отмеченным входным индексам сохраняет линейность и порядок мостов. Проверь цепи, циклы, параллельные рёбра, петли, несвязность и изолированные корни. Независимый эталон удаляет каждое ребро или вершину и пересчитывает компоненты BFS.

Задача 2: максимальная перевозка Эдмондсом–Карпом

Реализуй maxFlow(V, capacityEdges, source, sink): Long для ориентированного графа с разными корректными источником и стоком. Ёмкости — неотрицательные Long. Верни максимальный поток, сохранив вход. Параллельные и встречные рёбра различаются; петли можно игнорировать, они не улучшают значение.

Без пути верни ноль. Если максимальный итог не помещается в Long, брось ArithmeticException. Не объединяй параллельные ёмкости в потенциально переполняющуюся ячейку.

Подсказка 1

Ранний маршрут может занять связь, нужную лучшей комбинации. Какой остаточный ход позволит отменить и перенаправить решение?

Подсказка 2

Храни пары прямого и обратного остаточных рёбер. BFS ищет увеличивающий путь с минимальным числом рёбер. Отправь минимум его ёмкостей, уменьши прямые остатки и увеличь парные обратные.

Решение и объяснение

Обратные остаточные рёбра кодируют отмену, а не новую исходную ёмкость. Каждое увеличение сохраняет ограничения и баланс потока. Когда BFS не достигает стока, остаточно достижимые вершины задают разрез с ёмкостью текущего потока; больший поток пересечь его не может.

data class CapacityEdge(val from: Int, val to: Int, val capacity: Long)

fun maxFlow(vertices: Int, edges: List<CapacityEdge>, source: Int, sink: Int): Long {
    require(vertices >= 0 && source in 0 until vertices && sink in 0 until vertices && source != sink)
    data class Residual(val to: Int, val reverse: Int, var capacity: Long)
    val graph = Array(vertices) { mutableListOf<Residual>() }
    for ((from, to, capacity) in edges) {
        require(from in graph.indices && to in graph.indices && capacity >= 0)
        if (from == to) continue
        val forward = Residual(to, graph[to].size, capacity)
        val backward = Residual(from, graph[from].size, 0)
        graph[from].add(forward); graph[to].add(backward)
    }
    val parent = IntArray(vertices) { -1 }
    val parentEdge = IntArray(vertices)
    var total = 0L
    while (true) {
        val queue = ArrayDeque<Int>()
        val touched = mutableListOf(source)
        parent[source] = source; queue.addLast(source)
        while (queue.isNotEmpty() && parent[sink] == -1) {
            val vertex = queue.removeFirst()
            for (index in graph[vertex].indices) {
                val edge = graph[vertex][index]
                if (edge.capacity == 0L || parent[edge.to] != -1) continue
                parent[edge.to] = vertex; parentEdge[edge.to] = index
                touched.add(edge.to); queue.addLast(edge.to)
            }
        }
        if (parent[sink] == -1) return total
        var amount = Long.MAX_VALUE
        var vertex = sink
        while (vertex != source) {
            val previous = parent[vertex]
            amount = minOf(amount, graph[previous][parentEdge[vertex]].capacity)
            vertex = previous
        }
        total = Math.addExact(total, amount)
        vertex = sink
        while (vertex != source) {
            val previous = parent[vertex]
            val edge = graph[previous][parentEdge[vertex]]
            edge.capacity -= amount
            val reverse = graph[vertex][edge.reverse]
            reverse.capacity = Math.addExact(reverse.capacity, amount)
            vertex = previous
        }
        for (visited in touched) parent[visited] = -1
    }
}

Кратчайшие по числу рёбер увеличения дают O(VE) итераций и O(VE²) поисковой работы для E логических рёбер. С подготовкой оценка — O(V+E+VE²), память — O(V+E). Родительские массивы инициализируются один раз, затем очищаются только затронутые записи: нет полного V-прохода после каждого увеличения при множестве изолированных вершин.

У каждой остаточной пары свой обратный индекс, поэтому параллельные и исходно встречные связи не смешиваются. Проверяемый итог принимает Long.MAX_VALUE одного ребра и отклоняет большую сумму. Оценка времени зависит от размера графа, а не числового значения потока.

Проверь отсутствие пути, узкое место, перенаправление через обратный остаток, нулевые ёмкости, параллельные и встречные связи, петли и переполнение. Для малых графов перебери все разрезы с источником и без стока и сравни минимальную сумму ёмкостей. Это независимо от выбора увеличивающих путей.

Сможешь объяснить без страницы?

Почему двунаправленный поиск раскрывает целые слои?
Чем конфликт нечётного цикла отличается от сильной компоненты?
Зачем Косарайю порядок завершения и обратные рёбра?
Почему неравенства моста и некорневой точки различаются?
Почему Хиерхольцер хранит использованные рёбра вместо вершин?
Как удвоенные предки дают логарифмический запрос?
Что означает обратная остаточная ёмкость и почему недостижимый сток доказывает оптимальность?

Тема освоена, если ты выбираешь точное свойство графа, сохраняешь его особое состояние и проверяешь результат по определяющему контракту.