Cod sursa(job #1414648)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 2 aprilie 2015 20:56:00
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <list>

#define NMAX 100005
#define MMAX 500005
using namespace std;

struct edge {
    int a, b;
    bool vis;

    edge (int _a = 0, int _b = 0, bool _vis = false): a(_a), b(_b), vis(_vis) {}

    inline int other (int node) {
        return a + b - node;
    }
} edges[MMAX];

list <int> graph[NMAX];

list <int> sol;
list <int> :: iterator before;

inline void expand (int node) {
    int new_node;
    while (!graph[node].empty())
        if (edges[graph[node].front()].vis)
            graph[node].pop_front();
        else {
            new_node = edges[graph[node].front()].other(node);
            edges[graph[node].front()].vis = true;
            graph[node].pop_front();

            node = new_node;
            sol.insert(before, node);
        }
}

inline void euler () {
    sol.push_back(1);

    for (list <int> :: iterator it = sol.begin(); it != sol.end(); it++) {
        before = (++ it); it--;
        expand(*it);
    }
}

int main()
{
    ifstream cin("ciclueuler.in");
    ofstream cout("ciclueuler.out");

    int n = 0, m = 0;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> edges[i].a >> edges[i].b;
        graph[edges[i].a].push_back(i);
        graph[edges[i].b].push_back(i);
    }

    euler();

    if (sol.size() != m + 1)
        cout << "-1\n";
    else {
        list <int> :: iterator it = sol.begin();
        it ++;

        cout << *it;
        for (it++; it != sol.end(); it++)
            cout << ' ' << *it;
        cout << '\n';
    }

    cin.close();
    cout.close();
    return 0;
}