Cod sursa(job #1111121)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 18 februarie 2014 17:23:28
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <cstdio>
#include <list>
#include <stack>

#define Nmax 100005

using namespace std;

int N, M, D[Nmax], Viz[Nmax];
list <int> G[Nmax], L;
stack <int> St;

void Citire()
{
    int x, y;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
        D[x]++;
        D[y]++;
    }
}

void DFS(int nod)
{
    list <int> :: iterator it;
    Viz[nod] = 1;
    Viz[0]++;
    for (it = G[nod].begin(); it != G[nod].end(); ++it)
        if (!Viz[*it])
            DFS(*it);
}

int Eulerian()
{
    for (int i = 1; i <= N; ++i)
        if (!Viz[i])
            DFS(i);
    if (Viz[0] != N)
        return 0;
    for (int i = 1; i <= N; ++i)
        if (D[i] % 2)
            return 0;
    return 1;
}

void Stergere(int x, int y)
{
    list <int> :: iterator it;
    D[x]--;
    D[y]--;
    G[x].pop_front();
    for (it = G[y].begin(); it != G[y].end(); ++it)
        if (x == *it)
        {
            G[y].erase(it);
            break;
        }
}

void Ciclu(int x)
{
    int y;
    while (!G[x].empty())
    {
        y = G[x].front();
        St.push(x);
        Stergere(x, y);
        x = y;
    }
}

void Rezolvare()
{
    int x = 1;
    if (!Eulerian())
    {
        printf("-1");
        return;
    }
    do
    {
        Ciclu(x);
        x = St.top();
        St.pop();
        L.push_back(x);
    }while (!St.empty());
}

void Afisare()
{
    int a;
    while (!L.empty())
    {
        a = L.front();
        L.pop_front();
        printf("%d ", a);
    }
}

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

    Citire();
    Rezolvare();
    Afisare();

    return 0;
}