Cod sursa(job #1736166)

Utilizator alex.craciunCraciun Alexandru alex.craciun Data 1 august 2016 12:52:41
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector <int> lv[100002],c;
stack <int> s;
int n,m,grad[100002];
FILE *f=fopen("ciclueuler.in","r");
void citire( )
{
    fscanf(f,"%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        lv[x].push_back(y);
        lv[y].push_back(x);
        ++grad[x];
        ++grad[y];
    }
}
int verif_grad( )
{
    for(int i=1;i<=n;i++)
        if(grad[i]%2!=0)
           return 0;
    return 1;

}
void elim(int n1,int n2)
{
    lv[n1].erase(find(lv[n1].begin(),lv[n1].end(),n2));
    lv[n2].erase(find(lv[n2].begin(),lv[n2].end(),n1));
}
int rez( )
{
    s.push(1);
    while(!s.empty())
    {
        int nod=s.top();
        if(lv[nod].size())
        {
            int nod1=lv[nod].back();
            elim(nod,nod1);
            s.push(nod1);
        }
        else
        {
            c.push_back(nod);
            s.pop();
        }
    }
}
int main()
{
    citire();
    if(verif_grad()==0)
        cout<<"-1";
    else
    {
        rez( );
        vector <int> :: iterator ii;
        c.pop_back();
        FILE *f1=fopen("ciclueuler.out","w");
        for(ii=c.begin();ii!=c.end();ii++)
            fprintf(f1,"%d ",*ii);
    }
    return 0;
}