Pagini recente » Cod sursa (job #516455) | Cod sursa (job #2223029) | Cod sursa (job #1272107) | Cod sursa (job #180002) | Cod sursa (job #954415)
Cod sursa(job #954415)
#include <stack>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
const int NMAX = 100011;
bool was[NMAX];
int d[NMAX];
vector<int> S, ans;
vector<int> G[NMAX];
inline int numberOfNodes(int x)
{
was[x] = true;
int count = 1;
for(auto& y : G[x])
{
if(!was[y])
count += numberOfNodes(y);
}
return count;
}
inline void euler(int x)
{
int y;
while(!G[x].empty())
{
y = G[x].back(); G[x].pop_back();
G[y].erase(find(G[y].begin(), G[y].end(), x));
S.push_back(x);
x = y;
}
}
int main()
{
int N, M, x, y, i;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
//freopen("input.in", "rt", stdin);
for(in >> N >> M; M; --M)
{
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
++d[x]; ++d[y];
}
for(i = 1; i <= N; ++i)
{
if(d[i] % 2)
{
out << "-1";
return EXIT_SUCCESS;
}
}
if(N != numberOfNodes(1)) {out << "-1"; return EXIT_SUCCESS;}
x = 1;
do {
euler(x);
ans.push_back(x = S.back()); S.pop_back();
}while(!S.empty());
copy(ans.rbegin(), ans.rend(), ostream_iterator<int>(out, " "));
}