Cod sursa(job #2458532)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 20 septembrie 2019 21:21:45
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 100001;
const int MMAX = 500001;
vector <int> G[NMAX];
vector <int> ciclu;
vector <int> stiva;
bool used[MMAX];
int from[MMAX], to[MMAX];
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;
}