Cod sursa(job #591871)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 25 mai 2011 19:33:57
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <list>

using namespace std;

vector <int> g[100001];
stack <int> s;
list <int> l;
int n,m,vis[100001];

bool odd_degree()
{
    int i;
    for (i=1;i<=n;++i)
        if (g[i].size()%2)
            return 1;
    return 0;
}

void dfs(int x)
{
    unsigned int i;
    for (i=0;i<g[x].size();++i)
        if (!vis[g[x][i]])
        {
            vis[g[x][i]]=1;
            dfs(g[x][i]);
        }
}

bool unconnected()
{
    int i;
    dfs(1);
    for (i=1;i<=n;++i)
        if (!vis[i])
            return 1;
    return 0;
}

void cycle(int x)
{
    int y;
    unsigned int i;
    while (g[x].size())
    {
        y=g[x][g[x].size()-1];
        s.push(x);
        g[x].pop_back();
        for (i=0;i<g[y].size();++i)
            if (g[y][i]==x)
                break;
        g[y][i]=g[y][g[y].size()-1];
        g[y].pop_back();
        x=y;
    }
}

int main()
{
    int i,x,y;
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%d %d\n",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if (odd_degree()||unconnected())
    {
        printf("-1\n");
        return 0;
    }
    do
    {
        cycle(x);
        x=s.top();
        s.pop();
        l.push_back(x);
    }
    while (!s.empty());
    for (;!l.empty();l.pop_front())
        printf("%d ",l.front());
    printf("\n");
    return 0;
}