Реши на C++: Разбейте рёбра неориентированного гра...

Ниже приведён один из возможных вариантов решения на C++, который находит разбиение рёбер связного неориентированного графа на минимальное число путей-трейлов (то есть путей, проходящих по рёбрам без повторений). Идея опирается на классический факт: минимальное число путей, покрывающих все рёбра в связном графе, равно

Краткое описание идеи:

1. Считаем степени всех вершин. Собираем множество $O$ вершин нечётной степени.
2. Если $O$ пусто (все вершины чётной степени), то достаточно одного пути, который является эйлеровым циклом (весь граф покрывается одним циклом).
3. Если вершин нечётной степени $2k$, то мы «спарим» эти вершины попарно (произвольно, так как весов нет, достаточно любой пары). Между каждой парой добавим фиктивное (виртуальное) ребро. Тогда у всех вершин станет чётная степень, и в таком (мульти)графе можно построить один эйлеров цикл.
4. Построив эйлеров цикл (или эйлеров путь, если вершин нечётной степени было ровно 2), мы «разрежем» полученный цикл на отдельные пути всякий раз, когда проходим по фиктивному ребру. В исходном графе такие разрезы соответствуют началу нового пути.
5. Получаем искомое разбиение рёбер на минимальное число путей.

Код на C++

cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Разбиение ребер связного неориентированного графа на минимальное число путей,
  которые покрывают все ребра без повторений.
  
  Идея:
  1) Найти вершины с нечетной степенью.
  2) Если таких вершин 0, строим один эйлеров цикл.
     Если 2k > 0, попарно добавляем "виртуальные" ребра между ними.
  3) В полученном мультиграфе все вершины будут иметь четную степень,
     следовательно существует эйлеров цикл (или путь).
  4) Построим этот цикл (путь) алгоритмом Хьерхольцера.
  5) При проходе по "виртуальным" ребрам начинаем новый путь в ответе.
*/

struct Edge {
    int to;      // Конечная вершина
    bool used;   // Использовалось ли ребро при построении эйлерова пути
    int pair_id; // Номер обратного ребра в списке смежности "to"
    bool is_fake; // Является ли ребро виртуальным (добавленным)
};

const int MAXN = 20000;
vector<Edge> adj[MAXN+1];  // adj[v] = список ребер, исходящих из v
int n, m;

// Добавляем неориентированное ребро (v-u), возможно "виртуальное".
void add_edge(int v, int u, bool fake=false) {
    Edge fwd{u, false, (int)adj[u].size(), fake};
    Edge bwd{v, false, (int)adj[v].size(), fake};
    adj[v].push_back(fwd);
    adj[u].push_back(bwd);
}

// Алгоритм Хьерхольцера для эйлерова цикла/пути
// Возвращает последовательность вершин эйлерова обхода.
vector<int> euler_tour(int start) {
    // Стеки для хранения пути
    stack<int> st;
    vector<int> res;
    st.push(start);

    while (!st.empty()) {
        int v = st.top();
        if (!adj[v].empty()) {
            // Пока есть ребро, проверяем его
            auto &e = adj[v].back();
            adj[v].pop_back();
            if (!e.used) {
                // Помечаем ребро и обратное ребро как использованные
                e.used = true;
                auto &rev = adj[e.to][e.pair_id];
                rev.used = true;
                // Уходим по ребру
                st.push(e.to);
            }
        } else {
            // Нет больше ребер из v - добавляем в результат и возвращаемся
            st.pop();
            res.push_back(v);
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    vector<int> deg(n+1, 0);

    // Читаем ребра
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add_edge(a, b, false);
        deg[a]++;
        deg[b]++;
    }

    // Ищем вершины с нечетной степенью
    vector<int> odd;
    for(int v = 1; v <= n; v++){
        if (deg[v] % 2 == 1) {
            odd.push_back(v);
        }
    }

    // Если число нечетных вершин 2k, тогда добавим k виртуальных рёбер
    // Спарим вершины произвольно
    for (int i = 0; i+1 < (int)odd.size(); i += 2){
        int v = odd[i];
        int u = odd[i+1];
        add_edge(v, u, true);
        deg[v]++;
        deg[u]++;
    }

    // Найдём вершину, с которой начнём эйлеров обход.
    // Если есть нечётные вершины, то после добавления пар ребер
    // фактически у нас вышла "даже" степень у всех, что даёт эйлеров цикл.
    // Можно начинать с любой вершины, которая имеет хотя бы одно ребро.
    // Найдём первую вершину с ненулевой степенью:
    int start = 1;
    while (start <= n && adj[start].empty()) {
        start++;
    }

    // Выполним алгоритм Хьерхольцера, получим эйлеров цикл/путь
    vector<int> tour = euler_tour(start);
    // tour - последовательность вершин (замкнутый цикл или путь).
    // Размер tour = число использованных рёбер + 1

    // Теперь "разрежем" эйлеров цикл на минимальное число путей, 
    // "обрывая" там, где переходим по фиктивному ребру.

    // Идём по последовательности tour, 
    // когда встречаем виртуальное ребро, начинаем новый путь.
    // Чтобы это сделать, нам надо, зная пару соседних вершин (tour[i], tour[i+1]),
    // понять, было ли ребро между ними виртуальным.
    // Но у нас в текущем виде в tour нет прямой пометки, какое ребро использовалось.
    // Поэтому проще собрать список рёбер на основе последовательности вершин.

    // Однако нам уже "потраченные" рёбра отмечены как used=true, 
    // и обратно их не достать напрямую в том порядке, 
    // поэтому трекать "было ли ребро fake" при самом обходе бывает проще
    // (например, сохранять при обходе индексы ребёр).
    // Но сделаем здесь другой трюк: проанализируем пару (v,w) подряд в tour 
    // и найдём соответствующее ребро. В процессе решения на больших данных
    // это может быть неэффективно, но с учётом лимитов m<=20000 ещё может сработать.
    // Для надёжности часто делают отдельный список на этапе обхода.

    // Вариант: Запишем сам эйлеров путь в процессе обхода вместе с ID рёбер.

    // --- Упростим: Вместо переделки кода перезаполним "used" флагами и пройдемся
    //    ещё раз тем же порядком, но делая пометки. ---

    // Для эффективности: при построении euler tour часто сохраняют 
    // "маршрут ребер" - список (vertex_from, edge_id). Ниже для наглядности
    // сделаем простой поиск подходящего ребра (не лучший, но компактный для примера).

    // Сначала восстановим все ребра как "неиспользованные" (понадобится второй проход)
    // Затем пройдем по tour подряд и будем искать ребро между tour[i] и tour[i+1].
    // Чтобы не проводить поиск в O(deg(v)), можно заготовить map<pair<int,int>> -> vector<edge_indices>,
    // но на m=20000 это тоже не страшно. Ради простоты кода оставим линейный поиск.

    // В любом случае минимальное число путей = max(1, odd.size()/2).

    // 1) Сбросим used
    for (int v = 1; v <= n; v++){
        for (auto &e : adj[v]) {
            // Оставим все как "неиспользованные" для второго прохода
            // Но мы больше не будем запускать эйлеров обход, так что pair_id можем игнорировать
            e.used = false;
        }
    }

    // 2) Пройдемся по tour, формируя пути
    vector<vector<int>> paths;
    vector<int> curPath; 
    curPath.push_back(tour[0]);

    for (int i = 0; i+1 < (int)tour.size(); i++){
        int v = tour[i], w = tour[i+1];
        // Найдем ребро (v->w), которое неиспользованное
        bool isFake = false;
        // Ищем среди списка adj[v]
        int idxFound = -1;
        for (int idx = 0; idx < (int)adj[v].size(); idx++){
            auto &e = adj[v][idx];
            if (!e.used && e.to == w) {
                e.used = true;
                // Пометим и обратное
                auto &rev = adj[w][e.pair_id];
                rev.used = true;
                isFake = e.is_fake; 
                idxFound = idx;
                break;
            }
        }
        // Добавляем вершину w в текущий путь
        curPath.push_back(w);
        // Если ребро виртуальное, значит начинаем новый путь
        if (isFake) {
            paths.push_back(curPath);
            curPath.clear();
            // Начинаем новый путь "с нуля": 
            // но обычно следующая вершина w станет началом нового пути
            // Т.к. curPath уже содержит w, после пуша мы очищаем,
            // надо добавить w как начало следующего пути:
            curPath.push_back(w);
        }
    }
    // Если остался непустой текущий путь, добавим
    if (!curPath.empty()) {
        // Возможен случай, когда последний переход был виртуальным, 
        // тогда curPath содержит одну вершину. Но это тоже корректно.
        paths.push_back(curPath);
    }

    // Вывод результатов
    // Минимальное число путей = paths.size(). Оно должно совпасть с
    // max(1, (odd.size())/2).
    cout << paths.size() << "\n";
    for (auto &p : paths) {
        for (int v : p) {
            cout << v << " ";
        }
        cout << "\n";
    }

    return 0;
}

Пояснения к решению

1. Определяем количество вершин нечётной степени. Пусть оно равно $2k$. Тогда в связном графе минимальное число искомых путей равно $\max(1, k)$.
2. Добавляем фиктивные (виртуальные) рёбра между парами вершин из множества нечётной степени, чтобы сделать их степень чётной. Порядок пар не важен, так как минимизировать «суммарную длину» не требуется – нужна лишь минимизация числа путей.
3. Находим эйлеров обход (цикл) в полученном (мульти)графе с помощью алгоритма Хьерхольцера. Теперь все вершины имеют чётную степень, значит существует цикл, проходящий по всем рёбрам ровно по одному разу.
   • Если изначально было $0$ нечётных вершин, получаем обычный эйлеров цикл за один проход.
   • Если было ровно $2$ нечётные вершины без явного «схлопывания» в цикл, то это эйлеров путь, но можно обрабатывать его как цикл, если мысленно добавить ребро между двумя нечётными вершинами.
4. «Режем» эйлеров цикл на отдельные пути в тех местах, где проходим по фиктивному ребру. Каждый такой отрезок в исходном графе – это искомый путь, покрывающий некоторую часть рёбер. Все рёбра исходного графа используются ровно один раз, а «виртуальные» рёбра мы не выводим в ответ – они нужны лишь для того, чтобы легко получить нужное разбиение.

На выходе получаем:

• Количество путей $= \max\bigl(1,\tfrac{\text{число нечётных вершин}}{2}\bigr)$.
• Перечисленные пути по вершинам. Порядок путей и порядок вершин в каждом пути может отличаться от примеров, но будет удовлетворять условию задачи.

Проверка на примере из условия

Пример из условия (граф на 7 вершинах и 7 рёбрах):

text
7 7
1 2
4 1
6 7
5 7
7 4
2 3
4 2

• Нечётные вершины: 2, 3, 4, 5, 6, 7 (всего 6 шт., т. е. $k=3$).
• Минимальное число путей = 3.
• Алгоритм найдёт одно эйлерово прохождение в расширенном графе (где добавили 3 виртуальных ребра), затем «разрежет» его в местах виртуальных рёбер. Результат будет выглядеть примерно так:

text
3
2 4 7 6
7 5
4 1 2 3

либо в другом порядке вершин/путей (что тоже корректно). Каждый из полученных путей проходит по рёбрам без повторений, а все рёбра исходного графа ровно один раз участвуют в каком-то пути.

Таким образом, данное решение находит корректное минимальное разбиение рёбер на пути.