Cod sursa(job #1255034)

Utilizator ZenusTudor Costin Razvan Zenus Data 4 noiembrie 2014 09:03:48
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <vector>
#include <set>
#include <stack>
#include <queue>

using namespace std;

#define NMAX 100007

multiset < int > G[NMAX];
vector < int > sol;
queue < int > Q;
stack < int > S;
bool marked[NMAX];
int N,M,X,node,i,Y,current;
bool flag;

bool conex()
{
    Q.push(1);
    marked[1]=true;

    bool flag=true;
    int node,i;

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

        for (set < int > :: iterator u=G[node].begin();u!=G[node].end();++u)
        {
            if (marked[*u]) continue;

            marked[*u]=true;
            Q.push(*u);
        }
        Q.pop();
    }

    for (i=1;i<=N;++i) flag&=marked[i];

    return flag;
}

void df(int node)
{
    int e=node;

    while (!G[e].empty())
    {
        S.push(e);

        current=*G[e].begin();
        G[current].erase(G[current].find(e));
        G[e].erase(G[e].begin());

        e=current;
    }
}

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

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

    G[X].insert(Y);
    G[Y].insert(X);
}

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

node=1;
while (!flag)
{
    df(node);

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

    sol.push_back(node);

    if (S.empty()) flag=true;
}

for (vector < int > :: iterator u=sol.begin();u!=sol.end();++u)
printf("%d ",*u);

return 0;
}