Cod sursa(job #1553497)

Utilizator DanBrezeanuBrezeanu Dan DanBrezeanu Data 19 decembrie 2015 22:42:37
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100005;

vector <int> G[NMAX];
int grad[NMAX];
stack <int> st;


void euler_valoare(int u)
{
    int v,k;

    while(!G[u].empty())
    {
        st.push(u);
        k=(int)G[u].size();
        v = G[u][k-1];

        G[u].pop_back();
        G[v].erase(find(G[v].begin(),G[v].end(),u));
        u=v;
    }
}




int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);

	int n , m , i,pos1,pos2,u=1;

	scanf("%d%d",&n,&m);

	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&pos1,&pos2);
		G[pos1].push_back(pos2);
		G[pos2].push_back(pos1);
		grad[pos1]++;
		grad[pos2]++;
	}

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

        do
        {
            euler_valoare(u);
            u=st.top();
            st.pop();
            printf("%d ",u);

        }while(!st.empty());


	return 0;

}