Cod sursa(job #1192939)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 30 mai 2014 11:54:36
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <list>
#include <stack>
#include <queue>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n,m,v[100011],sol[100011];
bool viz[100011];

list<int> L[100011];
list<int>::iterator it;
stack<int> S;
deque<int> Q;

bool conex(){
    int nod,i,nr=1;
    Q.push_back(1);
    viz[1]=true;
    while(!Q.empty()){
        nod=Q.front(); Q.pop_front();
        for(it=L[nod].begin();it!=L[nod].end();it++)
            if(!viz[*it])
                viz[*it]=true,Q.push_back(*it),nr++;
    }
    if(nr==n)
        return true;
    else
        return false;
}

void stergere(int x,int y){
	v[x]--,v[y]--;
	L[x].pop_front();
	for(it=L[y].begin();it!=L[y].end();it++){
		if(*it==x){
			L[y].erase(it);
			break;
		}
	}
}

void euler(int nod){
	int w;
	while(!L[nod].empty()){
		w=L[nod].front();
		S.push(nod);
		stergere(nod,w);
		nod=w;
	}
}

int main(void){
    register int i,j,x,y,nod;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
        v[x]++,v[y]++;
    }
    for(i=1;i<=n;i++)
        if(v[i]%2){
            g<<"-1";
            return 0;
        }

    if(!conex()){
        g<<"-1";
        return 0;
    }

    //determinam ciclul
    nod=1;
    do{
    	euler(nod);
        nod=S.top(),S.pop();
        sol[++sol[0]]=nod;
    }while(!S.empty());
    for(i=sol[0];i>0;i--)
		g<<sol[i]<<" ";
    f.close();
    g.close();
    return 0;
}