Cod sursa(job #1333386)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 3 februarie 2015 08:29:02
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <stack>
#include <vector>
#define Nmax 100010

using namespace std;

stack <int> S;
vector <int> g[100010];
int n,m,i,x,y,nod,crt;
bool flag;

void dfs(int nod)
{
    vector < int > :: iterator u;
    while (!g[nod].empty())
    {
        S.push(nod);
        crt=g[nod][g[nod].size()-1];
        g[nod].pop_back();

        for (u=g[crt].begin(); u!=g[crt].end(); ++u)
            if (*u==nod)
            {
                g[crt].erase(u);
                break;
            }

        nod=crt;
    }
}

int main()
{
    freopen("cicluleuler.in","r",stdin);
    freopen("cicluleuler.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);
    }

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


    nod=1;
    while (!flag)
    {
        dfs(nod);
        nod=S.top();
        S.pop();
        printf("%d ", nod);

        if (S.empty()) flag=true;
    }


    return 0;
}