Не проходит по времени, помогите разобраться почему долго работает

[VladKB1]

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

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

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

История Принцессы
ограничение по времени на тест: 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 вершины с нечётной степенью (ведь вершин с нечётной степенью будет всегда чётное количество, да?).

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

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

//#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;
}

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

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

[VladKB1]

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

//#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;
}

[Black Fregat]

Ещё добрый совет, может быть, неожиданный: когда счёт идёт на миллисекунды, операция "cin >>" в цикле может съесть существенную часть времени. Лучше использовать scanf в стиле С.