Pagini recente » Cod sursa (job #629575) | Cod sursa (job #2393712) | Cod sursa (job #81872) | Cod sursa (job #1716709) | Cod sursa (job #2377195)
#include <unordered_set>
#include <stack>
#include <iostream>
using namespace std;
struct graph
{
unordered_multiset<int>* adj;
int s;
graph(const int n)
{
adj = new unordered_multiset<int>[n];
s = n;
}
void add_edge(const int u, const int v)
{
adj[u].insert(v);
adj[v].insert(u);
}
};
stack<int> path;
stack<int> st;
void euler_path(graph& g)
{
st.push(0);
while(!st.empty())
{
int u = st.top();
if(g.adj[u].empty())
{
path.push(st.top());
st.pop();
}
else
{
int v = *g.adj[u].begin();
st.push(v);
g.adj[u].erase(g.adj[u].find(v));
g.adj[v].erase(g.adj[v].find(u));
}
}
}
int n, m;
int main()
{
FILE* f = fopen("ciclueuler.in","r");
FILE* g = fopen("ciclueuler.out","w");
fscanf(f,"%d%d\n",&n,&m);
graph gr(n);
for(int i= 0; i < m; i++)
{
int u, v;
fscanf(f,"%d%d\n", &u, &v);
u--; v--;
gr.add_edge(u,v);
}
for(int i = 0; i < n; i++)
if(gr.adj[i].size()%2==1)
{
fprintf(g,"-1");
return 0;
}
euler_path(gr);
path.pop();
while(!path.empty())
{
fprintf(g,"%d ", path.top()+1);
path.pop();
}
return 0;
}