Cod sursa(job #2103927)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 10 ianuarie 2018 22:17:52
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <vector>
#include <utility>
#define MAXM 500000
#define MAXN 100000
using namespace std;
vector <pair <int,int> > v[MAXN];
vector <int> sol;
bool viz[MAXM],seen[MAXN];
int st[MAXM+1],vf;
int main()
{
    FILE *fin,*fout;
    fin=fopen("ciclueuler.in","r");
    fout=fopen("ciclueuler.out","w");
    int n,m,x,y,muchie,nr;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        x--;y--;
        v[x].push_back(make_pair(y,i));
        v[y].push_back(make_pair(x,i));
    }
    for(int i=0;i<n;i++)
        if((v[i].size()&1))
        {
            fprintf(fout,"-1");
            return 0;
        }
    vf=1;nr=n;
    while(vf)
    {
        x=st[vf-1];
        if(!seen[x])
            seen[x]=true,nr--;
        if(v[x].size())
        {
            y=v[x].back().first;
            muchie=v[x].back().second;
            v[x].pop_back();
            if(!viz[muchie])
                viz[muchie]=true,st[vf++]=y;
        }
        else
            sol.push_back(st[--vf]+1);
    }
    if(nr)
        fprintf(fout,"-1");
    else
        for(unsigned int i=0;i<sol.size()-1;i++)
            fprintf(fout,"%d ",sol[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}