Cod sursa(job #1485690)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 12 septembrie 2015 18:22:40
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#define Nmax 100010
#define pb push_back
using namespace std;

int n,m1,grad[Nmax],viz[Nmax];
vector<int>::iterator it;
vector<int> m[Nmax],rez;
queue<int> c;
stack<int> s;

int is_eulerian()
{
    int okgrad=1,i,nrvf=0,nod;
    c.push(1); viz[1]=1; nrvf=1; if(grad[1]%2==1) okgrad=0;
    if(okgrad==0) return 0;
    else
    {
        while(!c.empty())
        {
            nod=c.front(); c.pop();
            for(it=m[nod].begin();it!=m[nod].end();it++)
            {
                if(grad[*it]%2==1) { okgrad=0; return 0; }
                if(!viz[*it]) { c.push(*it); nrvf++; viz[*it]=1; }
            }
        }
        if(nrvf==n) return 1;
               else return 0;
    }

}

void sterge(int n1,int n2)
{
    grad[n1]--; grad[n2]--;
    m[n1].erase(m[n1].begin());
    for(it=m[n2].begin();it!=m[n2].end();it++)
        if(*it==n1)
        {
            m[n2].erase(it);
            break;
        }
}

void euler(int n1)
{
    int n2;
    while(true)
    {
        if(m[n1].size()==0) break;
        n2=m[n1].front();
        s.push(n1);
        sterge (n1,n2);
        n1=n2;
    }
}

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    int n1,n2,i,v;
    scanf("%d%d",&n,&m1);
    for(;m1;m1--)
    {
        scanf("%d%d",&n1,&n2);
        m[n1].pb(n2);
        m[n2].pb(n1);
        grad[n1]++; grad[n2]++;
    }

    if(!is_eulerian()) printf("-1\n");
    else
    {
        v=1;
        do
        {
            euler(v);
            v=s.top(); s.pop();
            rez.pb(v);
        } while(!s.empty());

        for(it=rez.begin();it!=rez.end();it++) printf("%d ",*it);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}