▲

3

▼

🌀 Поиск Эйлерова пути с удалением рёбер (алгоритм Хирхольцера)

leetcoder, 30-11-2024 , 363

Задача на выходные - 2097. Valid Arrangement of Pairs

Описание задачи 📜

Нужно переставить заданные пары [starti,endi] так, чтобы получилось корректное расположение,
где для каждой пары i: endi−1=starti​. Гарантируется, что такое расположение существует.

Обзор решения 🛠

Для решения задачи используется алгоритм Хирхольцера, который позволяет построить Эйлеров путь (или цикл) в ориентированном графе. Основная идея — удалять рёбра во время обхода, что упрощает структуру данных и предотвращает повторное использование рёбер.

Ключевые шаги 🚀

1. Построение графа:
   • Граф представляется в виде списка смежности (HashMap<i32, Vec<i32>>), где каждая вершина хранит список своих исходящих рёбер.
   • Параллельно вычисляются разницы степеней вершин (входящих и исходящих рёбер) для определения начальной вершины пути.
2. Поиск начальной вершины:
   • Начальная вершина — это вершина с положительным балансом исходящих рёбер. Если таких нет, берётся любая вершина из входных данных.
3. Итеративный DFS с удалением рёбер:
   • Вместо стандартного рекурсивного DFS используется итеративный подход с явным стеком. Это повышает эффективность памяти и скорость.
   • При посещении вершины рёбра удаляются из списка смежности, что гарантирует, что каждое ребро используется ровно один раз.
4. Построение результата:
   • После завершения обхода путь разворачивается, чтобы восстановить корректный порядок вершин. Затем формируются пары для возвращаемого результата.

Анализ Сложности 🔍

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

Исходный код

use std::collections::HashMap;

impl Solution {
    pub fn valid_arrangement(pairs: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        // Step 1: Build adjacency list and in-degree map
        let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
        let mut indegree: HashMap<i32, i32> = HashMap::new();

        for pair in &pairs {
            let (start, end) = (pair[0], pair[1]);
            graph.entry(start).or_default().push(end);
            *indegree.entry(start).or_insert(0) += 1;
            *indegree.entry(end).or_insert(0) -= 1;
        }

        // Step 2: Find the start node (node with positive degree)
        let mut start = pairs[0][0];
        for (&node, &degree) in &indegree {
            if degree > 0 {
                start = node;
                break;
            }
        }

        // Step 3: Perform Eulerian path construction using an iterative DFS
        let mut stack: Vec<i32> = vec![start];
        let mut path: Vec<i32> = Vec::new();

        while let Some(node) = stack.last() {
            if let Some(neighbors) = graph.get_mut(node) {
                if !neighbors.is_empty() {
                    let next_node = neighbors.pop().unwrap();
                    stack.push(next_node);
                } else {
                    path.push(stack.pop().unwrap());
                }
            } else {
                path.push(stack.pop().unwrap());
            }
        }

        // Step 4: Build the result from the path
        let mut result: Vec<Vec<i32>> = Vec::new();
        for i in (1..path.len()).rev() {
            result.push(vec![path[i], path[i - 1]]);
        }

        result
    }
}