Pagini recente » Statistici Alex Preda (AsthenichDog390) | Cod sursa (job #2756) | Cod sursa (job #1482212) | Istoria paginii utilizator/waizdor | Cod sursa (job #1557791)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
vector <int> G[100001];
vector <int> ans;
stack<int> S;
bool viz[100001];
int grad[100001];
int nNoduri,nMuchii;
void dfs(int nod)
{
viz[nod] = true;
for(vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
if(!viz[*it])
dfs(*it);
}
bool conexCheck()
{
int numComp = 0;
for(int i = 1; i <= nNoduri; ++i)
{
if(!viz[i])
{
numComp++;
if(numComp > 1) return false;
dfs(i);
}
}
return true;
}
int main()
{
int x,y;
f >> nNoduri >> nMuchii;
for(int i = 1; i <= nMuchii; ++i)
{
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
++grad[x];
++grad[y];
}
bool flag = true;
for(int i = 1; i <= nNoduri; ++i)
if(grad[i] % 2)
flag = false,i = nNoduri + 1;
if(flag && conexCheck())
{
int nod,urmNod;
S.push(1);
while(!S.empty())
{
nod = S.top();
if(G[nod].size())
{
urmNod = G[nod].back();
S.push(urmNod);
G[nod].pop_back();
G[urmNod].erase(find(G[urmNod].begin(), G[urmNod].end(), nod) );
}
else
{
nod = S.top();
ans.push_back(nod);
S.pop();
}
}
flag = false;
for(vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)
if(!flag) flag = true;
else g << *it << " ";
}
else
g << "-1";
return 0;
}