Pagini recente » Cod sursa (job #671284) | Cod sursa (job #2443656) | Cod sursa (job #2340841) | Cod sursa (job #677535) | Cod sursa (job #591752)
Cod sursa(job #591752)
#include <cstdio>
#include <list>
#include <deque>
#include <stack>
#include <vector>
using namespace std;
FILE *f,*g;
int gr[100100];
bool bif[100100];
stack <int > S;
deque <int> q;
vector <int> sol;
list <int> a[100100];
int i,n,m,x,y;
bool ok;
void bf() {
int w;
q.push_back(1);
bif[1]=true;
while (q.size()>0) {
w=q.front();
q.pop_front();
for (list <int>::iterator j=a[w].begin();j!=a[w].end();j++)
if (bif[*j]==false) {
bif[*j]=true;
q.push_back(*j);
}
}
}
void del(int j, int i) {
gr[j]--; gr[i]--;
a[i].pop_front();
for (list<int>::iterator q=a[j].begin();q!=a[j].end();q++)
if (*q==i) {
a[j].erase(q);
break;
}
}
void euler(int i) {
int j;
while (true) {
if (a[i].empty()) {
break;
}
j=a[i].front();
S.push(i);
del(j,i);
i=j;
}
}
int main() {
f=fopen("ciclueuler.in","r");
g=fopen("ciclueuler.out","w");
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++) {
fscanf(f,"%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
gr[x]++;
gr[y]++;
}
ok=true;
for (i=1;i<=n;i++)
if (gr[i]%2==1)
ok=false;
bf();
for (i=1;i<=n;i++)
if (bif[i]==false)
ok=false;
if (ok==false) {
fprintf(g,"-1");
fclose(g);
return 0;
}
int x;
//fprintf(g,"1 ");
x=1;
do {
euler( x );
x = S.top(); S.pop();
sol.push_back( x );
}
while( !S.empty() );
for (i=0;i<sol.size();i++)
fprintf(g,"%d ",sol[i]);
fclose(g);
return 0;
}