Cod sursa(job #716336)

Utilizator Sm3USmeu Rares Sm3U Data 18 martie 2012 17:15:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define nMax 100010

using namespace std;

int n;
vector <int> graf[nMax];
vector <int> afis;
int grad[nMax];
int viz[nMax];
stack <int> stiva;

void citire()
{
    int m;
    scanf ("%d %d", &n, &m);
    while (m --){
        int x;
        int y;
        scanf ("%d %d", &x, &y);
        graf[x].push_back (y);
        graf[y].push_back (x);
        grad[x] ++;
        grad[y] ++;
    }
}

void DFS(int nod)
{
    for (unsigned int i = 0; i < graf[nod].size(); ++ i){
        if (viz[graf[nod][i]] == 0){
            viz[graf[nod][i]] = 1;
            DFS(graf[nod][i]);
        }
    }
}

void verificareGrafEulerian()
{
    DFS(1);
    for (int i = 1; i <= n; ++ i){
        if (viz[i] == 0){
            printf ("-1\n");
            exit(0);
        }
        if (grad[i] %2 != 0){
            printf ("-1\n");
            exit(0);
        }
    }
}

void sterge(int unde, int ce)
{
    for (unsigned int i = 0; i < graf[unde].size(); ++ i){
        if (graf[unde][i] == ce){
            graf[unde].erase(graf[unde].begin() + i);
            return;
        }
    }
}

void rez(int v)
{
    while (!graf[v].empty()){
        int x = graf[v].back();
        graf[v].pop_back();
        stiva.push(v);
        sterge(x,v);
        v = x;
    }
}

void GrafEulerian()
{
    int v = 1;
    do{
        rez(v);
        v = stiva.top();
        stiva.pop();
        afis.push_back (v);
    }while (!stiva.empty());
}

int main()
{
    freopen ("ciclueuler.in", "r", stdin);
    freopen ("ciclueuler.out", "w", stdout);

    citire();
    verificareGrafEulerian();
    GrafEulerian();
    for (int i = 0; i < afis.size(); ++ i){
        printf ("%d ", afis[i]);
    }
    printf ("\n");

    return 0;
}