Cod sursa(job #1847019)

Utilizator mariakKapros Maria mariak Data 14 ianuarie 2017 11:23:41
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 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;

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

void euler(int node)
{
    while(G[node].size())
    {
        S.push(node);
        int son = G[node].back();
        G[node].pop_back();
        for(int i = 0; i < G[son].size(); ++ i)
        if(G[son][i] == node){
            G[son].erase(G[son].begin() + i);
            break;
        }
        node = son;
    }
}
void solve()
{
    bool dfs = true;

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

    for(int node = 1; !S.empty() || dfs; dfs = 0, printf("%d ", node)){
        euler(node);
        node = S.top();
        S.pop();
    }

}
int main()
{
    read();
    solve();
    return 0;
}