Cod sursa(job #1450436)

Utilizator tudormaximTudor Maxim tudormaxim Data 13 iunie 2015 13:32:42
Problema Ciclu Eulerian Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int nmax = 100005;
vector < pair<int,int> > graf[nmax];
vector <int> sol;
int n, m;
void read()
{
    ifstream fin ("ciclueuler.in");
    int i, x, y;
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x >> y;
        graf[x].push_back(make_pair(y,i));
        graf[y].push_back(make_pair(x,i));
    }
    fin.close();
}
bool eulerian()
{
    int i, nod, fiu, muchie;
    bool out[nmax];
    for(i=1; i<=n; out[i]=0, i++)
        if(graf[i].size()%2==1) return 0;

    stack<int> st;
    st.push(1);
    while(!st.empty())
    {
        nod=st.top();
        while(!graf[nod].empty() && out[graf[nod].back().second])
            graf[nod].pop_back();
        if(graf[nod].size())
        {
            fiu=graf[nod].back().first;
            muchie=graf[nod].back().second;
            out[muchie]=1;
            st.push(fiu);
        }
        else
        {
            sol.push_back(nod);
            st.pop();
        }
    }
    return 1;
}
void printf()
{
    ofstream fout ("ciclueuler.out");
    if(eulerian()==0) fout << "-1";
    else
    {
        for(int i=0; i<sol.size()-1; i++)
            fout << sol[i] << " ";
    }
    fout.close();
}
int main()
{
    read();
    printf();
    return 0;
}