Cod sursa(job #1320851)

Utilizator rebound212Mihnea Savu rebound212 Data 18 ianuarie 2015 16:38:47
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> sol,G[100001];
int n, m, x, y, c[500001], i;
 int verif()
{
    for (int i=1; i<=n; i++)
        if (G[i].size()%2) return 0;
    return 1;
}
 void ciclu()
{
 c[++c[0]]=1;
 int x,y;
   while(c[0])
   {
        x=c[c[0]];
        if(!G[x].empty())
        {
             y=G[x].back();
             c[++c[0]]=y;
             G[x].pop_back();
             G[y].erase(find(G[y].begin(),G[y].end(),x));
        }
        else
        {
            c[0]--;
            sol.push_back(x);
        }
   }
}
int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    if (!verif()) printf("-1\n");
    else
    {
        ciclu();
        for (i=0; i<sol.size()-1; i++)
            printf("%d ", sol[i]);
    }
    return 0;
}