Cod sursa(job #1885409)

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

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

void DFS()
{
    int x,k;

    stiva[vf = 1] = 1;
    while(vf)
    {
        x = stiva[vf];
        if(add[vf]) { sol[++T] = x; add[vf] = 0; }
        if(idx[x] == a[x].size()) --vf;
        for(; idx[x] < a[x].size(); ++idx[x])
        {
            k = a[x][ idx[x] ];
            if(!deja[k]){
                ++idx[x];
                add[vf] = deja[k] = 1;
                stiva[++vf] = st[k]+dr[k]-x;
                break;
            }
        }
    }
}

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();
    for(i = 1; i <= T; ++i) fprintf(fout,"%d ",sol[i]);


return 0;
}