Cod sursa(job #2458531)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 20 septembrie 2019 21:20:41
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 100001;
vector <int> G[NMAX];
vector <int> ciclu;
vector <int> stiva;
bool used[NMAX];
int from[NMAX], to[NMAX];
int main()
{
    FILE *fin, *fout;
    int nod,i,n,m,a,b,edge,next;
    fin = fopen("ciclueuler.in","r");
    fout = fopen("ciclueuler.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=0;i<m;i++){
        fscanf(fin,"%d %d",&a,&b);
        G[a].push_back(i);
        G[b].push_back(i);
        from[i]=a;
        to[i]=b;
    }
    for(i=1;i<=n;i++)
        if(G[i].size()%2 == 1){
            fprintf(fout,"-1\n");
            return 0;
        }
    stiva.push_back(1);
    while(!stiva.empty()){
        nod = stiva.back();
        if(!G[nod].empty()){
            edge = G[nod].back();
            G[nod].pop_back();
            if(!used[edge]){
                used[edge] = true;
                next = from[edge];
                if(next == nod)
                    next = to[edge];
                stiva.push_back(next);
            }
        }
        else{
            stiva.pop_back();
            ciclu.push_back(nod);
        }
    }
    for(i=0;i<ciclu.size()-1;i++)
        fprintf(fout,"%d ",ciclu[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}