Cod sursa(job #2261507)

Utilizator BogdanAlexandruBogdan-Alexandru Dig BogdanAlexandru Data 16 octombrie 2018 11:56:22
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <queue>
#include <deque>
#include <vector>
#define mp make_pair
#include <bitset>
using namespace std;
FILE *f,*g;
vector < pair <int,int> > graf[100090];
bitset <500010> fr;
deque<int> coada;
int n,m;
void READ()
{
    int x,y,i;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        graf[x].push_back(mp(y,i));
        graf[y].push_back(mp(x,i));
    }
}
int TEST_ZERO()
{
    int i;
    for(i=1;i<=m;i++)
        if(graf[i].size()%2)
            return 0;
    return 1;
}
void DFS(int NOD)
{
    int poz,vecin;
    while(graf[NOD].size())
    {
        vecin=graf[NOD].back().first;
        poz=graf[NOD].back().second;
        graf[NOD].pop_back();
        if(!fr[poz])
        {
            fr[poz]=1;
            DFS(vecin);
        }
    }
    coada.push_back(NOD);
}
void WRITE()
{
    fprintf(g,"%d ",coada.back());
    coada.pop_back();
    while(coada.size()!=1)
    {
        fprintf(g,"%d ",coada.back());
        coada.pop_back();
    }
}
int main()
{
    f=fopen("ciclueuler.in","r");
    g=fopen("ciclueuler.out","w");
    READ();
    if(!TEST_ZERO())
    {
        fprintf(g,"-1");
        return 0;
    }
    DFS(1);
    WRITE();
    fclose(f),fclose(g);
    return 0;
}