Pagini recente » Cod sursa (job #2588646) | Cod sursa (job #3194982) | Cod sursa (job #3131533) | Cod sursa (job #264231) | Cod sursa (job #1813448)
/**
* Program that determines wether a given multigraph
* is eulerian or not. Prints :
*
* (a) A nodes sequence that determines the
* eulerian cycle if it is one
* (b) -1 if it is not
*
* EUCLIDIAN CYCLE = a cycle where every edge
* is visited only once
*
* Created by Tudor Avram on 22/11/16.
*/
#include<cstdio>
#include<vector>
#include<list>
#define pf push_front
#define pb push_back
#define N_MAX 100010
#define M_MAX 500010
using namespace std;
vector <int> G[N_MAX];
list <int> Q;
inline void Euler(int x)
{
int y;
vector <int> :: iterator it;
Q.pb(x);
while (!Q.empty())
{
x=Q.front();
if (G[x].empty())
{
Q.pop_front();
printf("%d ",x);
}
else
{
y=G[x].back();
Q.pf(y);
G[x].pop_back();
for (it=G[y].begin();it!=G[y].end();++it)
if (*it==x)
{
G[y].erase(it);
break;
}
}
}
}
inline void Read_Data()
{
int N,M,x,y,i;
bool ok=true;
scanf("%d%d",&N,&M);
for (i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
}
for (i=1;i<=N;i++)
if (G[i].size()%2==1) ok=false;
if (ok) Euler(1);
else printf("-1");
printf("\n");
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
Read_Data();
fclose(stdin);
fclose(stdout);
return 0;
}