Pagini recente » Cod sursa (job #3260874) | Cod sursa (job #942926) | Cod sursa (job #2598970) | Cod sursa (job #28562) | Cod sursa (job #1016229)
#include <cstdio>
#include <vector>
#include <stack>
#define nodes 100002
using namespace std;
vector <int> adj[nodes], sol;
stack <int> st;
int n, m, x, y, node, node2, degree[nodes];
bool visited[nodes];
inline void DFS(int node)
{
visited[node] = 1;
for(vector <int> :: iterator it = adj[node].begin(); it!=adj[node].end(); ++it)
if( !visited[*it] )
DFS(*it);
}
inline bool is_connected()
{
DFS(1);
for(int i=1; i<=n; ++i)
if( !visited[i] )
return 0;
return 1;
}
inline bool is_eulerian()
{
if( !is_connected() )
return 0;
for(int i=1; i<=n; ++i)
if( degree[i] % 2)
return 0;
return 1;
}
inline void delete_edge(int node, int node2)
{
--degree[node]; --degree[node2];
adj[node].erase(adj[node].begin());
for(vector <int > :: iterator it = adj[node2].begin(); it != adj[node2].end(); ++it)
if( (*it) == node )
{
adj[node2].erase( it );
return ;
}
}
inline void euler(int node)
{
while( true )
{
if( adj[node].empty() )
break ;
st.push(node);
node2 = adj[node].front();
delete_edge(node, node2);
node = node2;
}
}
int main()
{
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
scanf("%d %d", &n, &m);
while ( m-- )
{
scanf("%d %d", &x, &y);
adj[x].push_back(y); ++degree[x];
adj[y].push_back(x); ++degree[y];
}
if( !is_eulerian() )
printf("-1\n");
else
{
node = 1;
do{
euler( node );
node = st.top();
st.pop();
sol.push_back(node);
} while ( !st.empty());
for(vector <int > :: iterator it = sol.begin(); it != sol.end(); ++it)
printf("%d ", *it);
printf("\n");
}
return 0;
}