Cod sursa(job #1098388)

Utilizator gabrielvGabriel Vanca gabrielv Data 4 februarie 2014 19:43:12
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <list>
#include <stack>
#include <vector>

using namespace std;

#define NMAX 100015

int N,M;

bool used[NMAX];

list < int > G[NMAX]; // Neighbours

stack < int > PEC; // Partial Eulerian Cicle

vector < int > Sol; // Solution


void Read()
{
    freopen("ciclueuler.in","r",stdin);
    scanf("%d%d",&N,&M);

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

void DFS(int node)
{
    used[node] = 1;

    for(list < int > :: iterator it = G[node].begin(); it!= G[node].end(); ++it)
        if(!used[*it])
            DFS(*it);
}

bool CheckIfGraphIsEulerian()
{
    DFS(1);

    for(int i=1;i<=N;i++)
        if(G[i].size()%2 || !used[i])
            return false;
    return true;
}

void DeleteNeighbour(int node1, int node2)
{
    G[node1].pop_front();

    for(list < int > :: iterator it = G[node2].begin(); it!= G[node2].end(); ++it)
        if(*it == node1)
        {
            G[node2].erase(it);
            return;
        }
}

void SearchCicle(int node)
{
    while(!G[node].empty())
    {
        PEC.push(node);
        int node2 = G[node].front();
        DeleteNeighbour(node,node2);
        node = node2;
    }
}

void Solve()
{
    int node = 1;

    do{
        SearchCicle(node);
        node = PEC.top();
        PEC.pop();
        Sol.push_back(node);
    }while(!PEC.empty());
}

void Print(bool IsEulerian)
{
    freopen("ciclueuler.out","w",stdout);

    if(IsEulerian)
        for(vector < int > :: iterator it = Sol.begin(); it!= Sol.end(); ++it)
            printf("%d ",*it);
    else
        printf("-1");
}

int main()
{
    Read();
    if(!CheckIfGraphIsEulerian())
        Print(false);
    else
    {
        Solve();
        Print(true);
    }
    return 0;
}