Эйлеров путь. Не проходит по времени

@vladKB · Регистрация: 20.08.2017

Студворк — интернет-сервис помощи студентам

Доброго времени суток!

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

Условие задачи:

История Принцессы
ограничение по времени на тест: 2.0 с
ограничение по памяти на тест: 256 МБ

Я нашёл Принцессу в подвале таверны, как и ожидал. После того, как она сделала ставки на турнир, мы поднялись наверх пропустить по стаканчику виски. Я надеялся выведать информацию о Драконе, ведь Принцесса в своё время частенько заходила к нему на Чай.

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

Под звуки голоса Принцессы я чувствовал, как тьма из углов таверны расползается и покрывает всё вокруг. Чувство реальности покидало меня. Не надо быть Добрым Волшебником, чтобы догадаться, что она подсыпала что-то мне в стакан. Пламя жизни внутри меня угасало, я провалился во тьму. Как ловко она перессорила тех принцев. Как же она это сделала? Никогда не пейте виски с Принцессой.

Входные данные
В первой строке записаны два целых числа через пробел: n и m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 2·10^5) — количество принцев и количество пар друзей среди них соответственно.

Далее в m строках через пробел записаны пары целых чисел ai и bi (1 ≤ ai < bi ≤ n) — пары номеров принцев, являющихся друзьями. Принцы нумеруются с единицы. Каждая пара представлена не более одного раза.

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

Во второй строке выведите k целых чисел через пробел — номера принцев в том порядке, в котором Принцесса должна с ними встречаться. Если ответов несколько, выведите любой из них.

Примеры:
входные данные
9 5
2 4
2 6
3 5
3 9
5 9
выходные данные
7
3 9 5 3 6 2 4

входные данные
4 5
1 2
1 3
1 4
2 4
3 4
выходные данные
6
4 3 1 4 2 1

Идея решения:
Здесь может быть несколько компонент связанностей, будем обрабатывать каждую по отдельности.

Предварительно при чтении посчитаем степень каждой вершины (то есть количество рёбер, которые есть у этой вершины (рёбра неориентированные)).

Затем при обработке очередной компоненты мы будем искать в ней эйлеров путь. Если вершин с нечётной степенью будет больше 2, то между любыми 2 вершинами с нечётной степенью создадим ребро. Будем так делать, пока у нас не останется 2 вершины с нечётной степенью (ведь вершин с нечётной степенью будет всегда чётное количество, да?).

Затем запустим поиск эйлерова пути из вершины с нечётной степенью (если такие есть, если нет, то с любой) и после того как путь будет найден и записан в стэк, будем искать следующую компоненту.

Ну, собственно вроде и всё, ниже код с комментариями.

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <iterator>
#include <utility>
#include <sstream>
 
 
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
 
using namespace std;
 
 
typedef long long ll;
 
vector <pair <ll, ll> > ss[111111]; // список связаности для хранения графа
ll n, m, i, a, b, k, stn, st[111111], stt[4444444], p[111111], f[111111], x, z;
 
void dfss(ll v) {     //красим компоненту в цвет x и записываем в стэк все вершины с нечётной степенью
    if (f[v] != 0 || v == -1) return;
    f[v] = x;
    z++;     // считает кол-во вершин
    if (p[v] % 2 != 0) st[++k] = v;     // запись в стэк
    for (ll j = 0; j < ss[v].size(); j++) dfss(ss[v][j].fi);     // обход
}
 
void dfs(ll v) {
    for (ll j = 0; j < ss[v].size(); j++) if (ss[v][j].fi != -1) { // распростронение, если ss[v][j].fi = -1, то значит дороги нету
        ll z = ss[v][j].fi; // запоминаем куда надо будет идти
        ss[v][j].fi = -1; // удаляем ребро
        ss[z][ss[v][j].se].fi = -1; // удаляем ребро
        dfs(z);
    }
 
    stt[++stn] = v; // ложим в ответ вершину
}
 
int main() {
    ios_base::sync_with_stdio(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
 
    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> a >> b;
        ss[a].push_back(mp(b,ss[b].size()));     //построение графа, 1 элемент пары содержит саму вершину куда нужно 
        ss[b].push_back(mp(a,ss[a].size()-1));  //распространяться, а 2 содержит индекс ребра ведущего из B в A
                             //граф же неорентированый, а рёбра нужно будет потом удалять, когда путь буду строить, для этого и пара
        p[a]++; p[b]++;     // считаем степени вершины
    }
 
    for (ll o = 1; o <= n; o++) if (f[o] == 0) {  // ищем ещё не закрашенную вершину, она будет в новой компоненте
        x++; z = 0; k = 0; // x - цвет которым красим, z - счётчик вершин в компоненте, k - счётчик вершин с нечётной степенью
        dfss(o); 
 
        if (z == 1) continue; 
 
        if (k > 2) for (i = 1; i <= k - 2; i += 2) {
            ss[st[i]].push_back(mp(st[i+1],ss[st[i+1]].size())); // создаём ребро между вершинами с нечётной степенью
            ss[st[i+1]].push_back(mp(st[i],ss[st[i]].size()-1)); 
        }
 
        b = o; // вершина с которой пойдём строить путь
        if (st[k] != 0) b = st[k];
        dfs(b);
    }
 
    cout << stn << endl;
    for (i = 1; i <= stn; i++) cout << stt[i] << " ";
    cout << endl;
    return 0;
}

Работать должно вроде бы быстро, не могу понять из-за чего всё же оно не пашет((

Всем заранее спасибо за любую помощь!

@MansMI · 20.08.2017, 07:09

откуда в в 1-м примере бл..во 3->6 ?

@vladKB · 20.08.2017, 11:39 **[ТС]**

первая компонетна состоит из 3 вершин 3 9 5, 2 компонента состоит тоже из 3 вершин 6 2 4. Мы просто находим путь в первой и потом путь во второй и записываем эти пути в ответ. Наша задача здесь "уничтожить все связи(рёбра)".

@MansMI · 20.08.2017, 11:46

Сообщение от vladKB

должна последовательно встречаться

как из 3 9 5 попасть в 6 2 4?

@vladKB · 20.08.2017, 14:19 **[ТС]**

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

Добавлено через 2 часа 5 минут
Всё задачу решил. Место хранения графа в векторе перевёл всё в set, могут быть случаи когда рёбер очень много а вершин не сильно и я постоянно буду от каждой вершины смотреть все рёбра и это долго, а так буду просто брать первое за log.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <iterator>
#include <utility>
#include <sstream>
 
 
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
 
using namespace std;
 
 
typedef long long ll;
 
//vector <pair <ll, ll> > ss[111111];
multiset <ll> ss[111111];
ll n, m, i, a, b, k, stn, x, z, st[4000000], stt[4000000], p[111111], f[111111];
 
void dfs(ll v) {
    if (f[v] != 0 || v == -1) return;
    f[v] = x; z++;
    if (p[v] % 2 != 0) st[++k] = v;
    for (set<ll>::iterator j = ss[v].begin(); j != ss[v].end(); j++) dfs(*j);
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    //freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
 
    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> a >> b;
        ss[a].insert(b);
        ss[b].insert(a);
        p[a]++; p[b]++;
    }
 
    for (ll o = 1; o <= n; o++) if (f[o] == 0) {
        x++; z = 0; k = 0;
        dfs(o);
 
        if (z == 1) continue;
 
        if (k > 2) for (i = 1; i <= k - 2; i += 2) {
            ss[st[i]].insert(st[i+1]); p[st[i]]++;
            ss[st[i+1]].insert(st[i]); p[st[i+1]]++;
        }
 
        b = o;
        if (st[k] != 0) b = st[k];
 
        ll v = 1; st[v] = b;
 
        while (v) if (p[st[v]] == 0) stt[++stn] = st[v--]; else {
            ll z = *ss[st[v]].begin();
 
            ss[st[v]].erase(ss[st[v]].begin());
            ss[z].erase(ss[z].find(st[v]));
 
            p[st[v]]--;
            p[z]--;
 
            st[++v] = z;
        }
    }
 
    cout << stn << endl;
    for (i = 1; i <= stn; i++) cout << stt[i] << " ";
    cout << endl;
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .

@MansMI 1617 / 1182 / 553 Регистрация: 08.01.2012 Сообщений: 4,561
	20.08.2017, 07:09
	откуда в в 1-м примере бл..во `3->6` ? 0

@vladKB 0 / 0 / 0 Регистрация: 20.08.2017 Сообщений: 3
	20.08.2017, 11:39 [ТС]
	первая компонетна состоит из 3 вершин 3 9 5, 2 компонента состоит тоже из 3 вершин 6 2 4. Мы просто находим путь в первой и потом путь во второй и записываем эти пути в ответ. Наша задача здесь "уничтожить все связи(рёбра)". 0