Cod sursa(job #1216064)

Utilizator ZenusTudor Costin Razvan Zenus Data 3 august 2014 10:57:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <list>

using namespace std;

#define NMAX 100005
#define PB push_back
#define MP make_pair
#define PII pair < int , int >

int degree[NMAX];
bool sel[NMAX];
int node=1,M,N,X,Y;
list < int > G[NMAX];
list < int > :: iterator itV;
stack < int > S;
list < int > sol;
queue < int > Q;

bool condition()
{
    queue < int > Q;
    int node;

    Q.push(1);
    sel[1]=true;

    while (!Q.empty())
    {
        node=Q.front();
        Q.pop();

        for (itV=G[node].begin();itV!=G[node].end();++itV)
        {
            if (sel[*itV]) continue;

            sel[*itV]=true;
            Q.push(*itV);
        }
    }

    for (int i=1;i<=N;++i)
    if (!sel[i] || (degree[i]&1))
    return false;

    return true;
}

void Delete(PII T)
{
    --degree[T.first];
    --degree[T.second];

    list < int > :: iterator itV;

    G[T.first].pop_front();

    for (itV=G[T.second].begin();itV!=G[T.second].end();++itV)
    if (*itV==T.first)
    {
        G[T.second].erase(itV);
        return ;
    }
}

void euler(int start)
{
    int i,node=start;

    while (!G[node].empty())
    {
        i=G[node].front();
        S.push(node);

        Delete(MP(node,i));
        node=i;
    }
}

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

scanf("%d%d",&N,&M);

while (M--)
{
    scanf("%d%d",&X,&Y);

    G[X].PB(Y);
    ++degree[X];

    G[Y].PB(X);
    ++degree[Y];
}

if (!condition())
{
    printf("-1\n");
    return 0;
}

do
{
    euler(node);

    node=S.top();
    S.pop();

    sol.PB(node);
} while (!S.empty());

for (itV=sol.begin();itV!=sol.end();++itV)
printf("%d ",*itV);

return 0;
}