Cod sursa(job #1305347)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 29 decembrie 2014 18:48:31
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define nmax 100001
#define pb push_back
using namespace std;
int n;
FILE *f=fopen("ciclueuler.in","r"),*g=fopen("ciclueuler.out","w");
vector <int> l[nmax];
stack <int> s;
int viz[nmax];
void df(int k)
{
    int i,x;
    viz[k]=1;
    for(i=0;i<l[k].size();i++)
    {
        x=l[k][i];
        if(!viz[x])
            df(x);
    }
}
int main()
{
    int i,j,m,x,y;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        l[x].push_back(y);
        l[y].push_back(x);
    }
    fclose(f);
    df(1);
    for(i=1;i<=n;i++)
        if(!viz[i]||l[x].size()%2!=0)
        {
            fprintf(g,"-1");
            return 0;
        }
    s.push(1);
    while(!s.empty())
    {
        x=s.top();
        if(!l[x].size())
        {
            fprintf(g,"%d ",x);
            s.pop();
        }
        else{
            y=l[x].back();
            s.push(y);
            l[x].pop_back();
            l[y].erase(find(l[y].begin(),l[y].end(),x));
            m--;
        }
    }
    fclose(g);
    return 0;
}