Cod sursa(job #2261332)

Utilizator BogdanAlexandruBogdan-Alexandru Dig BogdanAlexandru Data 16 octombrie 2018 10:20:22
Problema Ciclu Eulerian Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <stdio.h>
#include <deque>
#include <queue>
#include <vector>
#define mp make_pair
using namespace std;
FILE *f,*g;
vector <pair <int,int> > graf[100001];
int viz[100010];
int n,m,k,DA=1,Nod;
deque<int> sol;
void Read()
{
    int i,x,y;
    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));///adaug vecinul si pozitia muchiei pentru a-mi fi
        graf[y].push_back(mp(x,i));///mai usor de eliminat
    }
    for(i=1;i<=n;i++)///daca am gasit un nod care are numarul de vecini impar
        if(graf[i].size()%2==1)
        {
            DA=0;
            break;
        }
}
void Solve(int Nod)
{
    int vec,poz;
    while(!graf[Nod].empty())///cat timp Nod are vecini
    {
        vec=graf[Nod].back().first;///imi salvez vecinul
        poz=graf[Nod].back().second;///pozitia muchiei
        graf[Nod].pop_back();///elimin vecinul si pozitia muchiei
        if(!viz[poz])///daca n-am mai trecut prin muchia respectiva
        {
            viz[poz]=1;///marchez ca vizitata
            Solve(vec);///si continui parcurgerea cu vecinul
        }
    }
    sol.push_back(Nod);///adaug in coada nodul
}
void Write()
{
    int i;
    fprintf(g,"%d ",sol.front());
    sol.pop_front();
    while(!sol.empty())
    {
       if(sol.front()!=1)
        fprintf(g,"%d ",sol.front());
       sol.pop_front();
    }
}
int main()
{
    f=fopen("ciclueuler.in","r");
    g=fopen("ciclueuler.out","w");
    int n,m,i,x,y;
    Read();
    if(!DA)
    {
        fprintf(g,"-1");
        return 0;
    }
    Solve(1);
    Write();
    fclose(f),fclose(g);
    return 0;
}