Pagini recente » Cod sursa (job #2636142) | Cod sursa (job #3129734) | Cod sursa (job #254092) | Cod sursa (job #2713936) | Cod sursa (job #1919593)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
#define NMAX 100005
#define DIM 100000
using namespace std;
vector< pair<int, int> > V[NMAX], C;
stack<int> S;
bool visited[NMAX * 5];
char buff[DIM];
int N, M, nodStart, poz = DIM - 1;
void citire();
bool conditieGradPar();
void dfsIterativ(int nod);
void getNumber(int &x) {
x = 0;
while(buff[poz] < '0' || buff[poz] > '9')
if(++poz == DIM) fread(buff, 1, DIM, stdin), poz = 0;
while('0' <= buff[poz] && buff[poz] <= '9') {
x = x * 10 + (buff[poz] - '0');
if(++poz == DIM) fread(buff, 1, DIM, stdin), poz = 0;
}
}
int main()
{
freopen("ciclueuler.in", "rt", stdin);
freopen("ciclueuler.out", "wt", stdout);
citire();
if(conditieGradPar()==0) printf("-1\n");
else dfsIterativ(nodStart);
}
void citire()
{
int u,v;
getNumber(N);
getNumber(M);
for(int i = 1; i <= M; i++){
getNumber(u);
getNumber(v);
V[u].push_back(make_pair(v, i));
V[v].push_back(make_pair(u, i));
}
}
bool conditieGradPar()
{
for(int i=1; i<=N; i++)
if(V[i].size() & 1)
return 0;
else if(!nodStart && V[i].size())
nodStart = i;
return 1;
}
void dfsIterativ(int nod)
{
int nodStiva, vecin, indMuchie;
S.push(nod);
while(!S.empty()) {
nodStiva=S.top();
if( !V[nodStiva].empty()){
vecin=V[nodStiva].back().first;
indMuchie = V[nodStiva].back().second;
V[nodStiva].pop_back();
if(!visited[indMuchie]) {
visited[indMuchie] = true;
S.push(vecin);
}
}
else{
S.pop();
if(S.empty() == false) printf("%d ", nodStiva);
}
}
printf("\n");
}