Cod sursa(job #1009464)

Utilizator cat_red20Vasile Ioana cat_red20 Data 13 octombrie 2013 11:43:49
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,c[500002],ce[500002],deg[100001],viz[100001],k,k1,p;
vector<int>v[100001];
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

void citire()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }
}

void df(int nod)
{
    viz[nod]=1;
    for(int i=0;i<v[nod].size();i++)
    {
        if(viz[v[nod][i]]==0)
        {
            df(v[nod][i]);
        }
    }
}

void ciclu(int nod)
{
    int x=nod,y;

    do
    {
            y=v[x][0];
            deg[x]--;
            deg[y]--;
            v[x].erase(v[x].begin());
            v[y].erase(find(v[y].begin(),v[y].end(),x));

            x=y;
            c[++k]=x;


    }while(x!=nod);
}

int main()
{
    citire();
    for(int i=1;i<=n;i++)
    {
        if(deg[i]!=0)
        {
            p=i;
            df(i);
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0 || deg[i]%2==1)
        {
            fout<<"-1";
            return 0;
        }
    }
    k=1;
    c[k]=p;
    do
    {
        if(deg[c[k]]>0)
            ciclu(c[k]);
        k1++;
        ce[k1]=c[k];
        k--;
    }while(k>0);

    for(int i=1;i<k1;i++)
    {
        fout<<ce[i]<<" ";
    }
    return 0;
}