Cod sursa(job #1847304)

Utilizator mariakKapros Maria mariak Data 14 ianuarie 2017 15:10:36
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
#define NMAX 100002
FILE *fin  = freopen("ciclueuler.in", "r", stdin);
FILE *fout = freopen("ciclueuler.out", "w", stdout);

using namespace std;
int N, M;
vector <int> G[NMAX];
stack <int> s;
stack <int> ans;
char buff[1 << 23];
int bufferIndex;

int readInt() {
    int ans = 0;
    while (buff[bufferIndex] < '0' || buff[bufferIndex] > '9') bufferIndex ++;
    while ('0' <= buff[bufferIndex] && buff[bufferIndex] <= '9')
        ans = ans * 10 + buff[bufferIndex ++] - '0';
    return ans;
}

void read()
{
    int a, b;
    N = readInt(); M = readInt();
    for(int i = 1; i <= M; ++ i)
    {
        a = readInt(); b = readInt();
        G[a].push_back(b);
        G[b].push_back(a);
    }
}

void solve()
{
    for(int i = 1; i <= N; ++ i)
        if((int)G[i].size() & 1){
            printf("-1\n");
            return;
        }

    s.push(1);
    while (!s.empty())
    {
        int node = s.top();
        if (G[node].size() == 0){
            s.pop();
            ans.push(node);
        }
        else{
            int son = G[node].back();
            G[node].pop_back();
            s.push(son);

            for (int i = 0; i < G[son].size(); ++ i)
                if (G[son][i] == node){
                    G[son].erase(G[son].begin() + i);
                    break;
            }
        }
    }

    while (ans.size() != 0)
    {
        int node = ans.top();
        ans.pop();
        printf("%d ", node);
    }
}
int main()
{
    fread(buff, 1, 1 << 23, stdin);
    read();
    solve();
    return 0;
}