Pagini recente » Cod sursa (job #2900349) | Cod sursa (job #1329309) | Cod sursa (job #2613097) | Cod sursa (job #2104452) | Cod sursa (job #1251534)
#include <fstream>
#include <bitset>
#include <vector>
#define In "ciclueuler.in"
#define Out "ciclueuler.out"
#define pb push_back
#define Nmax 100005
#define Mmax 500005
using namespace std;
int n;
vector< int >graf[Nmax];
bitset< Mmax >uz;
int st[Mmax], dr[Mmax], traseu[Mmax];
///st[i] = capatul stang al muchiei i
///dr[i] = capatul drept al muchiei i
inline void Citire()
{
int m ,i;
ifstream f(In);
f >> n >> m;
for( i = 1 ; i <= m; i++)
{
f>> st[i] >> dr[i];
graf[ st[i] ].pb(i);
graf[ dr[i] ].pb(i);
}
}
inline bool Este_Eulerian()
{
int i;
for(i = 1;i <= n ;i++)
if(graf[i].size()&1)
return false;
return true;
}
inline void Dfs(int nod)
{
for(vector<int>::iterator it = graf[nod].begin();it != graf[nod].end();it++)
if(uz[*it]==false)//daca muchia nu este utilizata
{
uz[*it] = true;//o marcam ca fiind utilizata
Dfs(st[*it]+dr[*it]-nod);//mergem in celalat capat al muchiei
}
traseu[++traseu[0]] = nod;
}
int main()
{
Citire();
ofstream g(Out);
if(Este_Eulerian()==0)
{
g<<"-1\n";
g.close();
return 0;
}
Dfs(1);
int i;
for(i = 1 ;i <= traseu[0];i++)
g<<traseu[i]<<" ";
g<<"\n";
g.close();
return 0;
}