Cod sursa(job #750077)
Utilizator | Data | 20 mai 2012 15:12:30 | |
---|---|---|---|
Problema | Ciclu Eulerian | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.82 kb |
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main(){
ifstream cinr ("ciclueuler.in");
ofstream cour ("ciclueuler.out");
int n,m,a,b,y,z;
cinr >> n; cinr >> m;
vector< vector<int> > g(n+1);
vector<int> p(n+1,0);
bool t;
for(int i=1; i<=m; i++){
cinr >> a;
cinr >> b;
g[a].push_back(b);
g[b].push_back(a);
p[a]++;
p[b]++;
}
for(int i=1; i<=n; i++){
if(p[i]%2){
cour << "-1";
return 0;
}
}
vector<int> q,r;
q.push_back(1);
while(!q.empty()){
y=q.back();
if(g[y].empty()){
r.push_back(y);
q.pop_back();
}
else {
z=g[y].back();
g[y].pop_back();
for(int i=0; i<g[z].size(); i++){
if(g[z][i]==y){
g[z][i]=g[z].back();
g[z].pop_back();
break;
}
}
q.push_back(z);
}
}
for(int i=1; i<r.size(); i++){ cour << r[i-1] << " "; }
cinr.close(); cour.close();
//cin.ignore(2);
return 0;
}