Cod sursa(job #1311297)

Utilizator dica69Alexandru Lincan dica69 Data 7 ianuarie 2015 22:28:21
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <list>
#include <queue>
#include <stack>

using namespace std;

FILE *f1,*f2;
list <int> a[100001],c;
list <int> ::iterator it;
queue <int> q;
stack <int> s;
int x,y,n,m,ok,nod,i;
int use [100001];

void BFS(int nod)
{q.push(nod);use[nod]=1;
while (!q.empty())
{nod=q.front();q.pop();
for (it=a[nod].begin();it!=a[nod].end();it++)
if (!use[*it])
{q.push(*it);
use[*it]=1;
}
}
}

void del(int x,int y)
{a[x].pop_front();
for (it=a[y].begin();it!=a[y].end();it++)
if (*it==x) {a[y].erase(it); break;}
}

int main()
{f1 = fopen("ciclueuler.in","r");
f2 = fopen("ciclueuler.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}
ok=1;
BFS(1);
for (i=2;i<=n;i++) if (!use[i]) {ok=0;break;}
if (ok)
for (i=1;i<=n;i++) if (a[i].size()%2!=0) {ok=0;break;}
if (ok)
{nod=1;
do
{
while (!a[nod].empty())
{x=a[nod].front();
s.push(nod);
del(nod,x);
nod=x;
}
nod=s.top();s.pop();
c.push_back(nod);
} while (!s.empty());

for (it=c.begin();it!=c.end();it++) fprintf(f2,"%d ",*it);

}
else {fprintf(f2,"-1");}

fclose(f1);
fclose(f2);

    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.