Cod sursa(job #1180226)

Utilizator andreiulianAndrei andreiulian Data 30 aprilie 2014 10:41:09
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int m,n,a,b,s[500005],u,sol[500005],U;
vector<int> v[100005];
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
void euler(int i);
int main()
{
    int i;
    in>>n>>m;
    for(i=1;i<=n;i++) v[i].push_back(0);
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        v[a].push_back(b);
        v[a][0]++;
        v[b].push_back(a);
        v[b][0]++;
    }
    for(i=1;i<=n;i++) if(v[i][0]%2==1) {out<<-1<<'\n'; return 0;}
    euler(1);
    for(i=1;i<U;i++) out<<sol[i]<<' ';
}
void euler(int i)
{
    int poz,w,u=1,j,e;
    s[u]=i;
    while(u>0)
    {
        while(v[s[u]][0])
        {
            poz=1;
            e=s[u];
            while(v[e][poz]==-1) poz++;
            w=v[e][poz];
            v[e][poz]=-1;
            v[e][0]--;
            j=1;
            while(v[w][j]!=e) j++;
            v[w][j]=-1;
            v[w][0]--;
            s[++u]=w;
        }
        sol[++U]=s[u];
        u--;
    }
}