Cod sursa(job #1552982)

Utilizator grimmerFlorescu Luca grimmer Data 18 decembrie 2015 23:48:59
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define NMAX 100000
int n,m,grad[100001];
vector<int> G[NMAX+5],sol;
stack<int> st;
void CicluEuler(int u){
	int v,j;
	while(!G[u].empty()){
		st.push(u);
		j=(int)G[u].size();
		v = G[u][j-1];
		G[u].pop_back();
		G[v].erase(find(G[v].begin(),G[v].end(),u));
		u=v;
	}
}
int main()
{
	int u,v,i;
	bool ok;
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
		grad[u]++;
		grad[v]++;
    }
    ok=1;
    for(i=1;i<=n;i++){
        if(grad[i]!=0 && grad[i]%2!=0)
            ok=0;
    }
    if(ok==1){
        u=1;
        do{
            CicluEuler(u);
            u=st.top();
            st.pop();
            printf("%d ",u);
        }while(!st.empty());
    }
    else
        printf("-1");
	/// de verificat daca e ciclu eulerian
    return 0;
}