Cod sursa(job #1212187)

Utilizator jul123Iulia Duta jul123 Data 23 iulie 2014 23:44:47
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<iostream>
#include<cstdio>
#include<deque>
#include<stack>

using namespace std;

deque<int>g[100005], sol;
stack<int> s;
int n, m;
int gr[100005], viz[100005];

void DF(int v)
{
    viz[v]=1;
    for(int i=0; i<g[v].size(); i++)
    {
        if(viz[g[v][i]]==0)
            DF(g[v][i]);
    }
}
bool verific()
{
    DF(1);
    for(int i=1; i<=n; i++)
        if(viz[i]==0)
            return 0;
   for(int i=1; i<=n; i++)
        if(gr[i]%2==1)
            return 0;
    return 1;
}
void ciclu(int v)
{
    int w;
    while(!g[v].empty())
    {
        w=g[v][0];
        s.push(v);
        gr[v]--;
        gr[w]--;
        g[v].pop_front();

        for(deque<int>::iterator it=g[w].begin(); it!=g[w].end(); it++)
        {
            if(*it=v) {
                g[w].erase(it);
                break;
            }
        }
        v=w;
    }
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("ciclueuler.in", "r");
    fout=fopen("ciclueuler.out", "w");

    int x, y;
    fscanf(fin, "%d %d", &n, &m);
    for(int i=0; i<m; i++)
    {
        fscanf(fin, "%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
    if(verific()==0)
        fprintf(fout, "-1");
    else {
    int v=1;
    do{
        ciclu(v);
        v=s.top();
        s.pop();
        sol.push_back(v);
    }while(!s.empty());
    for(int i=sol.size()-1; i>=0; i--)
    {
        fprintf(fout, "%d ", sol[i]);
    }
    }
}