Cod sursa(job #673310)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 4 februarie 2012 11:57:18
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<stack>
#include<list>
using namespace std;

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

list<int> l,g[100010];
stack<int> s;

int main() {
	int n,m,a,b,i,v=1,w;
	list<int>::iterator it;
    
    in >> n >> m;
	
    for(;m;--m) {
        in >> a >> b;
		
        g[a].push_back(b);
        g[b].push_back(a);
    }
	
    for(i = 1; i <= n; ++i) {
        if(g[i].size()&1) {
            out << "-1\n";
            return 0;
        }
    }
	
    do {
        while(!g[v].empty()) {
			
            w = g[v].front();
            g[v].pop_front();
            s.push(v);
			
            for(it=g[w].begin(); it!=g[w].end(); ++it) {
				
                if(*it==v) {
                    g[w].erase(it);
                    break;
                }
            }
            v=w;
        }
        v=s.top();
        s.pop();
        l.push_front(v);
		
    } while(!s.empty());

    for(it=l.begin(); it!=l.end(); ++it)
        out << *it << " ";

	return 0;
}