Реши на C++: В городе есть N площадей, соединенн...

Ниже приведён пример решения на C++, которое находит маршрут почтальона минимальной длины (фактически решается классическая задача нахождения Эйлерова пути/цикла).

Основные идеи решения:

1. Считываем граф. У нас неориентированные улицы (рёбра), но в входных данных каждое ребро может дублироваться дважды: из вершины $i$ в $j$ и из $j$ в $i$. Чтобы не хранить каждое ребро по два раза, при вводе учитываем ребро $(i, j)$ только в одном порядке, например, если $i < j$.

2. Подсчитываем степень (число рёбер) у каждой вершины. В неориентированном графе эйлеров путь/цикл существует, только если:

   • Все вершины чётной степени (тогда существует эйлеров цикл, начинать можно с любой вершины с ненулевой степенью);
   • Ровно две вершины имеют нечётную степень (тогда существует эйлеров путь, начинать надо с одной из этих двух нечётных вершин, а закончить в другой).

   Если не выполняется ни одно из этих условий, выводим $-1$.

3. Строим Эйлеров путь (или цикл) алгоритмом ХIERHOLZER'а (Hierholzer):

   • Выбираем стартовую вершину:
     • Если есть 2 вершины нечётной степени, то начинаем с одной из них.
     • Если все вершины чётные, начинаем с любой вершины, у которой есть хотя бы одно ребро.
   • Итеративно «обходим» рёбра, помечая их как использованные; когда в текущей вершине рёбер не остаётся, записываем её в выходной маршрут и «возвращаемся» по стеку.

4. В итоге получаем порядок вершин в эйлеровом пути. Длина этого пути по количеству пройденных рёбер будет равна общему числу улиц (рёбер) в графе (то есть каждая улица пройдена ровно один раз).

5. Выводим:

   • В первую строку — число рёбер $M$ в маршруте.
   • Во вторую строку — список вершин (их будет $M+1$ в эйлеровом пути).

Обратите внимание, что по условию «не более трёх вершин нечётной степени» в неориентированном связном графе фактически означает, что таких вершин либо 0, либо 2 (так как общее число вершин нечётной степени в любом неориентированном графе всегда чётно). Если окажется, что таких вершин не 0 и не 2, выводим $-1$.

Код на C++

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

/*
  Решаем задачу нахождения Эйлерова пути (или цикла) в неориентированном графе.
  - Если в графе ровно 0 или 2 вершины нечётной степени, такой путь/цикл существует.
  - Если же другое количество нечётных вершин, решения нет (-1).
  
  Алгоритм:
  1) Считываем N.
  2) Для каждой вершины i (1..N) считываем m_i, а затем m_i пар (v, w) — здесь w нам для самого
     обхода не нужен, так как эйлеров путь зависит лишь от структуры рёбер.
     Однако в условии сказано, что ребро между i и v может встречаться и со стороны i, и со стороны v.
     Чтобы хранить каждое ребро ровно один раз, добавляем его в список, только если i < v.
  
  3) Подсчитываем степень каждой вершины (deg[i]).
  4) Проверяем, сколько вершин имеют нечётную степень.
     - Если 0, строим эйлеров цикл (старт — любая вершина с ненулевой степенью).
     - Если 2, стартуем из одной из двух нечётных вершин.
     - Иначе выводим -1 и завершаем.
  
  5) Строим путь алгоритмом Хьерхольцера (Hierholzer) с использованием стека.
  6) Выводим результат.
*/

// Глобальные структуры хранить не обязательно, но для удобства сделаем их статическими:
static const int MAXN = 100000;

// Список рёбер (u, v). Идентификатор ребра — это индекс в этом векторе.
vector<pair<int,int>> edges; 

// adjacency[v] будет хранить пары (u, id_ребра), где u — соседняя вершина, а id_ребра — индекс ребра в массиве edges
vector<vector<pair<int,int>>> adjacencyList;

// Показывает, использовано ли ребро (чтобы не проходить по нему дважды)
vector<bool> usedEdge;

// Степени вершин
vector<int> deg;

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

    int N;
    cin >> N;
    adjacencyList.resize(N+1);
    deg.resize(N+1, 0);

    // Считаем общее количество введённых "пар" (должно быть 2*M, если M - число рёбер)
    // Но мы сразу будем добавлять рёбра, если i < v.

    // Перебираем строки от i=1 до i=N
    // Каждая строка: m_i, а затем m_i пар (v, length).
    // length нам не нужен для построения эйлерова пути, но считать придётся, чтобы "пропустить" во входе.
    // Храним ребро лишь один раз (i < v).
    
    for(int i = 1; i <= N; i++){
        int m_i;
        cin >> m_i;
        for(int j = 0; j < m_i; j++){
            int v, w;
            cin >> v >> w; // длину w сейчас не используем, она не влияет на сам маршрут (только на стоимость)
            if(i < v){
                // Добавляем ребро (i, v) в список
                int edge_id = (int)edges.size();
                edges.push_back({i, v});
                // В список смежности добавляем в обе стороны
                adjacencyList[i].push_back({v, edge_id});
                adjacencyList[v].push_back({i, edge_id});
                // Увеличиваем степень
                deg[i]++;
                deg[v]++;
            } else if(i > v){
                // Аналогичное ребро уже учтено при рассмотрении вершины v (где v < i).
                // Ничего не делаем
            } else {
                // i == v быть не должно (нет петель по условию)
                // Игнорируем, или можно было бы выводить ошибку
            }
        }
    }

    // Теперь у нас есть список рёбер edges и список смежности adjacencyList.
    // Проверяем степени: ищем количество нечётных вершин
    vector<int> oddVertices;
    for(int i = 1; i <= N; i++){
        if(deg[i] % 2 == 1){
            oddVertices.push_back(i);
        }
    }

    // Если нечётных вершин ни 0, ни 2, решения нет
    if(!(oddVertices.size() == 0 || oddVertices.size() == 2)){
        cout << -1 << "\n";
        return 0;
    }

    // Выбираем стартовую вершину:
    int start = 1; // по умолчанию
    if(!oddVertices.empty()){
        // Если 2 нечётных вершины, стартуем с одной из них
        start = oddVertices[0];
    } else {
        // Если все степени чётные, то ищем любую вершину с ненулевой степенью (иначе граф вообще без рёбер, но по условию хотя бы одно ребро есть)
        // на случай, если, к примеру, вершина 1 вдруг оказалась изолированной
        bool found = false;
        for(int i = 1; i <= N; i++){
            if(deg[i] > 0){
                start = i;
                found = true;
                break;
            }
        }
        if(!found){
            // Значит рёбер нет, но по условию "В городе есть хотя бы одна улица" это маловероятно.
            // На всякий случай обработаем:
            cout << -1 << "\n";
            return 0;
        }
    }

    // Теперь строим эйлеров путь/цикл из start
    usedEdge.assign(edges.size(), false);
    
    // Алгоритм Хьерхольцера (итеративный, чтобы не переполнить стек):
    vector<int> path;      // итоговый путь (последовательность вершин)
    stack<int> st;
    st.push(start);

    while(!st.empty()){
        int v = st.top();
        // Пока есть рёбра, ведущие из v, пытаемся идти дальше
        // Но нужно найти ребро, которое ещё не использовано
        bool foundNext = false;
        while(!adjacencyList[v].empty()){
            auto [u, eID] = adjacencyList[v].back();
            adjacencyList[v].pop_back();
            if(!usedEdge[eID]){
                // Нашли неиспользованное ребро
                usedEdge[eID] = true; 
                st.push(u);
                foundNext = true;
                break;
            }
        }
        // Если не нашли ни одного рёбра для продолжения, то "возвращаемся" и записываем вершину в путь
        if(!foundNext){
            st.pop();
            path.push_back(v);
        }
    }

    // Полученный path — это эйлеров путь (в порядке обхода).
    // Он уже в правильном порядке (мы добавляли вершину, когда "заканчивали" с ней).
    // Длина такого пути по рёберному счету — это количество использованных рёбер = edges.size().

    int M = (int)edges.size();
    // Выводим
    if(M == 0){
        // Если не осталось рёбер, значит что-то не так: хотя бы одна улица должна быть.
        // Но если вдруг (на совсем крайний случай), выведем -1.
        cout << -1 << "\n";
        return 0;
    }

    // Эйлеров путь содержит M+1 вершину
    cout << M << "\n";
    for(int i = 0; i < (int)path.size(); i++){
        cout << path[i] << ( (i+1 < (int)path.size()) ? ' ' : '\n');
    }

    return 0;
}

Пояснения к коду:

1. Чтение графа:

   • Мы читаем для каждой вершины $i$ список рёбер (куда идёт и длина).
   • Чтобы каждое ребро не дублировать, включаем его в структуру данных, только если $i < v$.

2. Определение наличия решения:

   • Считаем количество вершин нечётной степени. В неориентированном графе их может быть только чётное число.
   • Если 0 вершин нечётной степени — строится эйлеров цикл (начинаем с любой вершины).
   • Если 2 — строится эйлеров путь (начинаем с одной из нечётных).
   • Иначе решения нет ($-1$).

3. Построение Эйлерова пути (алгоритм Хьерхольцера):

   • Используем стек, чтобы не уходить в глубокую рекурсию (при числе рёбер до 100 000 это важно).
   • Пока из текущей вершины есть неиспользованные рёбра, «спускаемся» по одному из них и помечаем ребро как использованное. Когда выйти дальше не можем, «возвращаемся» (pop из стека) и добавляем текущую вершину в итоговый маршрут.

4. Вывод:

   • В первой строке — число рёбер $M$ в искомом маршруте (каждая улица пройдена ровно один раз).
   • Во второй строке — вершины в порядке обхода (их будет $M+1$).

Таким образом, мы получаем требуемый минимальный маршрут, проходящий по каждой улице ровно один раз (что эквивалентно минимальной суммарной длине, так как каждая дорога «включается» не более одного раза). Если же такой маршрут невозможен по условию (число нечётных вершин не 0 и не 2), выводим $-1$.