Cod sursa(job #1489499)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 21 septembrie 2015 11:54:07
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
using namespace std;
const int NMAX=100002;
vector<int> g[NMAX], st;
int u, v, n, m, i;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
void erase_edge(int node, int neighbour)
{
    int nr=g[node].size();
    for(int i=0; i<nr; i++)
        if(g[node][i]==neighbour)
        {
            g[node].erase(g[node].begin()+i);
            return;
        }
}
void euler()
{
    int node, neighbour;
    st.push_back(1);
    while(st.size())
    {
        node=st.back();
        if(g[node].size())
        {
            neighbour=g[node].back();
            g[node].pop_back();
            erase_edge(neighbour,node);
            st.push_back(neighbour);
        }
        else
        {
            out<<node<<' ';
            st.pop_back();
        }
    }
}
int main()
{
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(i=1; i<=n; i++)
        if(g[i].size()%2||g[i].empty())
        {
            out<<"-1";
            return 0;
        }
    euler();
    return 0;
}