Pagini recente » Cod sursa (job #1324132) | Cod sursa (job #116932) | Cod sursa (job #51588) | Cod sursa (job #2204322) | Cod sursa (job #782388)
Cod sursa(job #782388)
#include <fstream>
#include <list>
#include <vector>
#define MAXN 100005
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n,m,u,v,x,y,d[MAXN];
list<int> G[MAXN];
vector<int> st,ciclu;
bool uz[MAXN];
bool eulerian();
void DFS(int p);
int main()
{
list<int>::iterator it;
int i;
f>>n>>m;
for(i=1;i<=m;i++){
f>>u>>v;
d[u]++;d[v]++;
G[u].push_back(v);
G[v].push_back(u);}
if(eulerian()){
st.push_back(1);
while(!st.empty()){
x=st.back();
if(!G[x].empty()){
y=G[x].front();
G[x].pop_front();
for(it=G[y].begin();*it!=x;it++);
G[y].erase(it);
st.push_back(y);}
else{
ciclu.push_back(x);
st.pop_back();}}
for(i=0;i<ciclu.size()-1;i++)
g<<ciclu[i]<<' ';}
else
g<<"-1\n";
f.close();
g.close();
return 0;
}
bool eulerian(){
int i;
DFS(1);
for(i=2;i<=n;i++)
if(!uz[i])
return 0;
for(i=1;i<=n;i++)
if(d[i]%2)
return 0;
return 1;}
void DFS(int p){
list<int>::iterator it;
uz[p]=1;
for(it=G[p].begin();it!=G[p].end();it++)
if(!uz[*it])
DFS(*it);}