Cod sursa(job #2119810)

Utilizator MirunaMMiruna Mitu MirunaM Data 1 februarie 2018 17:47:07
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> lista[100001];
int n,vc[100001];
void citire()
{
    int i,n1,n2,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&n1,&n2);
        vc[n1]++;
        vc[n2]++;
        lista[n1].push_back(n2);
        lista[n2].push_back(n1);
    }
}
int st[100002],sol[100001];
void eulerian()
{   int i,pp,j,k,nod,urm;
    pp=1;
    for( i=1;i<=n;i++)
        if(vc[i]%2==1)
            pp=0;
    if(pp==0)
        printf("-1");
    else
    {
        i=0;
        k=1;
        st[k]=1;
        while(k>0)
        {
            nod=st[k];
            if(lista[nod].size()!=0)
            {
                urm=lista[nod].back();
                k++;
                st[k]=urm;
                lista[nod].pop_back();
                vector <int>::iterator it;
                it=find(lista[urm].begin(),lista[urm].end(),nod);
                lista[urm].erase(it);
            }
            else
            {
                i++;
                sol[i]=st[k];
                k--;
            }
        }
    }
    for(int j=1;j<i;j++)
        printf("%d ",sol[j]);
}


int main()
{
    freopen("ciclueulerian.in","r",stdin);
    freopen("ciclueulerian.out","w",stdout);
    citire();
    eulerian();
    return 0;
}