Cod sursa(job #2309738)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 29 decembrie 2018 18:30:03
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

stack <int> st;
vector <int> v[100010];
int grad[100010],n,m,a[500010],sol;

void del (int node1, int node2)
{

    int nod=v[node1].size();
    int i;
    for (i=0;i<nod;i++) if (v[node1][i]==node2)
    {
        v[node1][i]=v[node1][nod-1];
        v[node1].pop_back();
        return;
    }

}


void euler (int node)
{
    int node2;
    st.push(node);
    while (st.size())
    {
        node=st.top();
        while (v[node].size())
        {
            node2=v[node][0];
            del(node, node2);
            del (node2, node);
            st.push(node2);
            node=node2;
        }
        sol++;
        a[sol]=st.top();
        st.pop();

    }
}



int main()
{
    int i;
    int x,y;
f>>n>>m;
for (i=1;i<=m;i++)
{
    f>>x>>y;
    v[x].push_back(y);
    v[y].push_back(x);
    grad[x]++;
    grad[y]++;

}
for (i=1;i<=n;i++) if (grad[i]%2==1) {g<<-1;return 0;}

euler(1);

for (i=1;i<=sol;i++) g<<a[i]<<" ";

    return 0;
}