Cod sursa(job #1803718)

Utilizator lauratalaatlaura talaat lauratalaat Data 11 noiembrie 2016 18:48:38
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct bine{
    int no,muchie;};
int n,m,k,vc1[500001],vc[100001];
vector<bine>v[100001];
vector<int>::iterator it;
int stiva[500001];
void citire(){
    int i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        bine p;
        p.no=y;
        p.muchie=i;
        v[x].push_back(p);
        p.no=x;
        v[y].push_back(p);
        vc[x]++;
        vc[y]++;
    }
}
void euler ( int nod ){
    int fiu,mu;
    while(v[nod].size()!=0&&vc1[v[nod].back().muchie]==1)
            v[nod].pop_back();
    while(v[nod].size()!=0){
        fiu=v[nod].back().no;
        mu=v[nod].back().muchie;
        vc1[mu]=1;
        k++;
        stiva[k]=fiu;
        v[nod].pop_back();
        /*it=find(v[fiu].begin(),v[fiu].end(),nod);
        v[fiu].erase(it);*/
        while(v[fiu].size()!=0&&vc1[v[fiu].back().muchie]==1)
            v[fiu].pop_back();
        nod=fiu;
    }
}
int main(){
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    citire();
    int pp=1,i;
    for(i=1;i<=n&&pp==1;i++)
        if(vc[i]%2==1)
            pp=0;
    if(pp==0)
        printf("-1\n");
    else{
        stiva[1]=1;
        k=1;

        while(k!=0){
            euler(stiva[k]);
            if(k>1)
                printf("%d ",stiva[k]);
            k--;

        }
    }
    return 0;
}