Complessità soluzione "matita"

Per risolvere questo problema (eulerian path, in soldoni) ho pensato di applicare l’algoritmo di Hierholzer[0], che in teoria è O(m). m in questo caso è al massimo 10^6 quindi dovrebbe andare tutto bene, ma va in TLE negli ultmi task e quindi prendo 75.

Come l’ho implementato, in pseudocodice:

eulerian_path(list sol, node u)
    sol = lista di nodi nell'eulerian path
    u = nodo corrente
    per ogni figlio v di u
        se in  sol non c'è l'arco (u, v) né l'arco (v, u)
        inserisci v in sol dopo u
        eulerian_path(sol, v)

Utilizzando un array di std::unordered_map<int, bool> per vedere se gli archi sono nella lista, l’accesso è O(1), quindi non dovrebbe essere quello il problema[1]. Una std::list ha inserimento in O(1), quindi di nuovo non credo sia questo il problema. Con O(2m) controlli (visto che controlla ogni arco e il suo contrario) e O(m) inserimenti (entrambe le parti di ogni arco), la complessità dovrebbe essere appunto O(m). Per stampare mi limito a scorrere la lista al contrario utilizzando un iterator, quindi di nuovo O(m). Cosa non ho considerato? Ne sto uscendo pazzo!

Il codice:

#include <bits/stdc++.h>

#define pb emplace_back

using namespace std;

const int MAX = 100000;

unordered_map<int, bool> vis[MAX];

vector<int> g[MAX];

list<int> sol;

int euler_path(list<int>::iterator it, int u) {
    for (auto v : g[u]) {
        if (!vis[v][u] && !vis[u][v]) {
            vis[v][u] = 1;
            vis[u][v] = 1;
            euler_path(sol.emplace(it, u), v);
        }
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    size_t n, m;
    int a, b;
    int start, end_;
    scanf("%d %d %d %d", &n, &m, &start, &end_);
    --start;
    --end_;

    for (size_t i = 0; i < m; i++) scanf("%d %d", &a, &b), g[--a].pb(--b), g[b].pb(a);

    euler_path(begin(sol), start);

    for (auto i = prev(end(sol)); i != begin(sol); i = prev(i)) printf("%d %d\n", *i + 1, *prev(i) + 1);
    printf("%d %d\n", *begin(sol) + 1, end_ + 1);


    return 0;
}

[0] https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm
[1] Nel caso peggiore è O(n), d’accordo, ma ho provato anche con una std::map con accesso sempre in O(\log n) e comunque dà 75. Un array di std::vector<bool> dà segnale 11, probabilmente perché troppo grande per i limiti di memoria. Una matrice statica è troppo grande per stare nello stack e fallisce la compilazione, una matrice dinamica con new fa 55 punti e un tot di segnali 11. Domanda bonus: quando ci sono matrici molto “sparse” (es. matrici di adiacenze di grafi, memo per DP con parametri potenzialmente molto grandi e diversi tra loro), conviene usare una std::unordered_map o altro?

Ecco il mio sorgente, spero ti possa essere utile
http://pastebin.com/GpmrswBv

Io l’ho risolto usando quello che dovrebbe essere lo stesso algoritmo descritto da te, però non ho avuto particolari problemi nell’implementazione. Utilizzo uno stack per eseguire una DFS con la differenza che rimuovo dallo stack il nodo da cui sono partito solo se da questo non ne ho potuti visitare altri (e in quel caso lo memorizzo in un altro stack, che mi serve per ricostruire il percorso da stampare in output).

Avevo provato a fare così ma prende comunque 75 :confused:

Hai ancora il codice? Probabilmente se va in TLE significa che riconsideri più volte gli stessi nodi, o qualche altra piccola svista :slight_smile:

Il codice è nel primo post xD

Il codice della versione che utilizza semplicemente uno stack, non ho capito bene perché dovresti volerlo risolvere con un unordered_map se non serve :slight_smile:

Ahh! Scusa ho capito male, ecco:

#include <bits/stdc++.h>

#define pb emplace_back

using namespace std;

const int MAX = 100010;

map<int, bool> vis[MAX];

vector<int> g[MAX];

int start, end_;

int m, n;

vector<int> sol;

bool has_neighbors(int u) {
    bool ans = 0;
    for (auto v : g[u]) {
        if (!vis[u][v] && !vis[v][u]) {
            ans = 1;
            break;
        }
    }
    return ans;
}

int euler_path() {
    stack<int> s;
    int u = start;
    while (has_neighbors(u) || !s.empty()) {

        if (!has_neighbors(u)) {
            sol.pb(u);
            u = s.top();
            s.pop();
        } else {
            s.push(u);
            for (auto v : g[u]) {
                if (!vis[v][u] && !vis[u][v]) {
                    vis[v][u] = 1;
                    vis[u][v] = 1;
                    u = v;
                    break;
                }
            }

        }
    }
}






int main()
{
    FILE *fin = fopen("input.txt", "r"), *fout = fopen("output.txt", "w");
    int a, b;
    fscanf(fin, "%d %d %d %d", &n, &m, &start, &end_);

    for (size_t i = 0; i < m; i++) fscanf(fin, "%d %d", &a, &b), g[a].pb(b), g[b].pb(a);

    euler_path();
    

    fprintf(fout, "%d %d\n", start, sol.back());
    for (size_t i = sol.size() - 1; i < sol.size() && i > 0; i--) fprintf(fout, "%d %d\n", sol[i], sol[i - 1]);


    return 0;
}

Anziché una funzione per verificare se ha dei vicini potresti utilizzare direttamente un flag booleano all’interno del ciclo in cui controlli se ce ne sono per aggiungere allo stack.
Comunque non mi è ben chiaro come mai utilizzi una map per indicare gli archi già disegnati e penso che possa essere questa a farti andare in TLE, non potresti semplicemente utilizzare un array di bool?

Una matrice statica di bool è troppo grande e non compila nemmeno, usando un std::bitset il correttore dà segnale 11 in tutti i testcase, un array di std::vector<bool> mi porta fino a 85 punti e poi occupa troppa memoria :confused:

EDIT: Risolto. Per i posteri, invece di usare una map ho reso “usato o meno” una proprietà dell’arco stesso (il grafo, invece di un array di vector di int, è diventato un array di vector di std::pair<int, bool>)

1 Mi Piace

Intendevo proprio una cosa di questo tipo :wink: