Pagini recente » Cod sursa (job #1065485) | Cod sursa (job #2069314) | Cod sursa (job #2285159) | Cod sursa (job #283820) | Cod sursa (job #2681363)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
struct muchie
{
int x, y;
bool viz;
int opposite(int a)
{
if(a == x)
return y;
return x;
}
} muchii[500005];
vector<int> graf[100005];
int nrViz[100005];
bool viz[100005];
int n, m;
stack<int> S;
void citire()
{
f>>n>>m;
for(int i = 0; i<m; i++)
{
f>>muchii[i].x>>muchii[i].y;
graf[muchii[i].x].push_back(i);
graf[muchii[i].y].push_back(i);
}
}
void dfs(int currNode)
{
viz[currNode] = true;
for(int i : graf[currNode])
{
int nod = muchii[i].opposite(currNode);
if(!viz[nod])
{
dfs(nod);
}
}
}
bool verif()
{
for(int i=1; i<=n; i++)
{
if(graf[i].size()%2 != 0 || (viz[i] == 0 && graf[i].size() != 0))
return false;
}
return true;
}
void parcInit()
{
S.push(1);
while(!S.empty())
{
int currNod = S.top();
if(!graf[currNod].empty())
{
int mch = graf[currNod].back();
graf[currNod].pop_back();
if(!muchii[mch].viz)
{
S.push(muchii[mch].opposite(currNod));
muchii[mch].viz = true;
}
}
else
{
if(S.size() > 1)
g<<currNod<<" ";
S.pop();
}
}
}
int main()
{
citire();
dfs(1);
if(!verif())
{
g<<"-1";
}
else
parcInit();
return 0;
}