Cod sursa(job #1579853)

Utilizator coolyonutzepure ionut coolyonutz Data 25 ianuarie 2016 09:47:05
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector <int> G[100001];
stack <int> st;
int n,m,grad[100001];

void eulerian(int u)
{
    int k,v;

    while(G[u].size())
    {
        k=(int)G[u].size();
        v=G[u][k-1];

        G[u].pop_back();
        G[v].erase(find(G[v].begin(),G[v].end(),u));

        st.push(u);

        u=v;
    }
}

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

    int i,poz1,poz2,u=1;

    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d",&poz1,&poz2);

        G[poz1].push_back(poz2);
        G[poz2].push_back(poz1);

        grad[poz1]++;
        grad[poz2]++;
    }

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

    do
    {
        eulerian(u);
        u=st.top();
        st.pop();

        printf("%d ",u);
    }
    while(!st.empty());
}