Cod sursa(job #1777983)

Utilizator delia_99Delia Draghici delia_99 Data 13 octombrie 2016 10:05:05
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#define NMAX 100000
using namespace std;

int n,m,i,node;
vector <int> G[NMAX+5];
vector <int> ::iterator it;
stack <int> S;
bool ok=true;

void euler(int node)
{
    int i,son;
    while(G[node].size())
    {
        S.push(node);
        son=G[node].back();
        G[node].pop_back();
        it=find(G[son].begin(),G[son].end(),node);
        G[son].erase(it);
        node=son;
    }
}

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

    scanf("%d%d",&n,&m);

    for(i=1; i<=m; ++i)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(i=1; i<=n; ++i)
        if(G[i].size()%2==1)
        {
            printf("-1\n");
            return 0;
        }

    node=1;
    while(!S.empty() || ok)
    {
        ok=false;
        printf("%d ",node);
        euler(node);
        node=S.top();
        S.pop();
    }

    return 0;
}