Cod sursa(job #2174544)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 16 martie 2018 12:30:57
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define LMAX 100001

using namespace std;
FILE *fin=fopen("ciclueuler.in","r");
FILE *fout=fopen("ciclueuler.out","w");

struct nod
{
    int x, poz;
};

vector<nod> G[LMAX];

int n, m;
int x, y;
int sol[5*LMAX+5], nrsol;
bool ok=1, use[5 * LMAX + 5];

void euler(int act);

int main()
{
    nod a;
    fscanf(fin,"%d %d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        fscanf(fin,"%d %d",&x,&y);
        a.poz = i;
        a.x = y;
        G[x].push_back(a);
        a.x = x;
        G[y].push_back(a);
    }
    for (int i=1;i<=n;i++)
        if (G[i].size()%2)
            {
              ok=0;
              break;
            }
    if (!ok)
        fprintf(fout,"-1\n");
        else
        {
         euler(1);
         for (int i=1;i<nrsol;i++)
              fprintf(fout,"%d ",sol[i]);
         fprintf(fout,"\n");
        }
    fclose(fin);
    fclose(fout);
}

void euler(int act)
{
    nod j;
    while (!G[act].empty())
    {
        j = G[act].back();
        G[act].pop_back();
        if (!use[j.poz])
        {
            use[j.poz] = 1;
            euler(j.x);
        }
    }
    sol[++nrsol] = act;
}