Cod sursa(job #1980033)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 11 mai 2017 23:16:25
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
list <int> G[Nmax];
int grd[Nmax];
stack <int> st;
int sol[Nmax];
int main()
{
    int n,m,k,i,j,x;
    f>>n>>m;
    for(k=1;k<=m;k++)
    {
        f>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
        grd[i]++;
        grd[j]++;
    }
    for(i=1;i<=n;i++)
    if(grd[i]%2)
    {
        g<<-1;
        return 0;
    }
    k=0;
    st.push(1);
    int w;
    list <int> :: iterator it;
    while(!st.empty())
    {
        x=st.top();
        if(!G[x].empty())
        {
            w=*G[x].begin();
            st.push(w);
            for(it=G[w].begin();*it!=x;it++);
            G[w].erase(it);
            G[x].erase(G[x].begin());

        }
        else
        {
            sol[++k]=x;
            st.pop();
        }
    }
    for(i=1;i<=m;i++)
        g<<sol[i]<<' ';

    return 0;
}