Cod sursa(job #1814074)

Utilizator stefanchistefan chiper stefanchi Data 23 noiembrie 2016 17:13:46
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define Nmax 100010
#define Mmax 500010
using namespace std;
vector <int> graf[Nmax];
int answer[Mmax];
int n,m,lim;

void ciclu_eulear()
{
    stack<int> s;
    s.push(1);
    while(!s.empty())
    {
        int i = s.top();
        s.pop();
        if(!graf[i].empty())
        {
            int vecin = graf[i].back();
            graf[i].pop_back();
            vector<int> :: iterator it;
            for(it = graf[vecin].begin(); *it != i ; it++);
            graf[vecin].erase(it);
            s.push(vecin);
        }
        answer[lim++] = i;
    }
}

void read()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y;
    for(int i = 0 ; i  < m ; i++)
    {
        scanf("%d %d",&x,&y);
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    for(int i =  1;  i <= n ; i++)
        if(graf[i].size() %2 == 1)
        {
            printf("-1");
            return;
        }
    ciclu_eulear();
    for(int i = 0 ; i < lim ; i++)
        printf("%d ",answer[i]);
}




int main()
{
    read();
    return 0;
}