Cod sursa(job #1256335)

Utilizator ZenusTudor Costin Razvan Zenus Data 6 noiembrie 2014 08:45:47
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <vector>
#include <set>
#include <stack>
#include <queue>

using namespace std;

#define NMAX 100007

vector < 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 (vector < 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][G[e].size()-1];
        G[e].pop_back();

        for (vector < int > :: iterator u=G[current].begin();u!=G[current].end();++u)
        if (*u==e)
        {
            G[current].erase(u);
            break;
        }

        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].push_back(Y);
    G[Y].push_back(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;
}