Cod sursa(job #1885394)

Utilizator silkMarin Dragos silk Data 19 februarie 2017 21:06:42
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define EMax 500000
#define NMax 100000
using namespace std;

vector<int> a[NMax+1];
int deja[EMax+1];
int sol[EMax+1];
int idx[NMax+1];
int st[EMax+1];
int dr[EMax+1];
int g[NMax+1];
int N,M,T;

void DFS(int x)
{
    int k;
    for(; idx[x] < a[x].size(); ++idx[x])
    {
        k = a[x][ idx[x] ];
        if(!deja[k]){
            deja[k] = 1;
            DFS(st[k]+dr[k]-x);
            sol[++T] = x;
        }
    }
}

int main(){
    FILE* fin = fopen("ciclueuler.in","r");
    FILE* fout = fopen("ciclueuler.out","w");

    int i,x,y;

    fscanf(fin,"%d %d",&N,&M);
    for(i = 1; i <= M; ++i)
    {
        fscanf(fin,"%d %d",&x,&y);
        st[i] = x;
        dr[i] = y;
        a[x].push_back(i);
        a[y].push_back(i);
        ++g[x]; ++g[y];
    }

    for(i = 1; i <= N; ++i)
    if(g[i] % 2) { fprintf(fout,"-1\n"); return 0; }

    DFS(1);
    for(i = 1; i <= T; ++i) fprintf(fout,"%d ",sol[i]);


return 0;
}