Cod sursa(job #878150)

Utilizator sebii_cSebastian Claici sebii_c Data 14 februarie 2013 03:01:51
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>

#include <algorithm>
#include <list>
#include <vector>

using namespace std;

const int MAXN = 100001;

list<int> G[MAXN];
vector<int> sol;

int deg[MAXN];
bool vis[MAXN];

void dfs(int node)
{
    vis[node] = true;
    list<int>::iterator it;
    for (it = G[node].begin(); it != G[node].end(); ++it) {
        if (vis[*it])
            continue;
        dfs(*it);
    }
}

void rem_edge(int v, int w)
{
    G[v].pop_front();
    list<int>::iterator it;
    for (it = G[w].begin(); it != G[w].end(); ++it)
        if (*it == v) {
            G[w].erase(it);
            break;
        }
}

void euler(int v)
{
    while (!G[v].empty()) {
        int w = *G[v].begin();
        rem_edge(v, w);
        euler(w);
    }
    sol.push_back(v);
}

int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        deg[x]++;
        G[y].push_back(x);
        deg[y]++;
    }

    dfs(1);
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) {
            printf("-1\n");
            return 0;
        }

    for (int i = 1; i <= n; ++i)
        if (deg[i] % 2 != 0) {
            printf("-1\n");
            return 0;
        }

    euler(1);
    reverse(sol.begin(), sol.end());
    for (int i = 0; i < sol.size() - 1; ++i)
        printf("%d ", sol[i]);
    printf("\n");

    return 0;
}