Pagini recente » Cod sursa (job #1100426) | Cod sursa (job #1936861) | Cod sursa (job #1979669) | Cod sursa (job #1006565) | Cod sursa (job #782653)
Cod sursa(job #782653)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector< pair<int,int> > lista[100005];
vector<int> v;
bool viz[500005];
stack<int> stiva;
void eulerian(int nod)
{
while(lista[nod].size())
{
// daca vecinul nu e vizitat ( adica nu am folosit muchia )
if( viz[lista[nod].back().first]==0)
{
viz[lista[nod].back().first]=1; // vizitez vecinul viz[indice]
//printf("Suntem la nodul : %d si mergem la: %d\n",nod,lista[nod].back().second);
int next_nod=lista[nod].back().second; // scot
lista[nod].pop_back();
eulerian(next_nod);
}
else
lista[nod].pop_back();
}
v.push_back(nod);
return;
}
int main()
{
int n,m;
freopen("ciclueuler.in","r", stdin);
freopen("ciclueuler.out","w", stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
//printf("%d %d\n",x,y);
lista[x].push_back(make_pair(i,y));
lista[y].push_back(make_pair(i,x));
}
for(int i=1;i<=n;i++)
if(lista[i].size()%2==1)
{
printf("-1");
return 0;
}
stiva.push(1);
while(!stiva.empty())
{
bool ok=true;
int nod=stiva.top();
while(lista[nod].size())
{
// daca vecinul nu e vizitat ( adica nu am folosit muchia )
if( viz[lista[nod].back().first]==0)
{
viz[lista[nod].back().first]=1; // vizitez vecinul viz[indice]
//printf("Suntem la nodul : %d si mergem la: %d\n",nod,lista[nod].back().second);
int next_nod=lista[nod].back().second; // scot
lista[nod].pop_back();
stiva.push(next_nod);
ok=false;
break;
}
else
lista[nod].pop_back();
}
if(!ok)
continue;
v.push_back(nod);
stiva.pop();
}
for(int i=v.size()-1;i>0;i--)
printf("%d ",v[i]);
fclose(stdin);
fclose(stdout);
return 0;
}