Pagini recente » Cod sursa (job #1077457) | Cod sursa (job #1048269) | Cod sursa (job #2236978) | Cod sursa (job #421984) | Cod sursa (job #589233)
Cod sursa(job #589233)
#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) {
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;
i=1;
while (1==1) {
if (a[i].empty()) {
break;
}
j=a[i].back();
a[i].pop_back();
del(j,i);
S.push(j);
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;
}