Pagini recente » Borderou de evaluare (job #264061) | Cod sursa (job #295583)
Cod sursa(job #295583)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 100005
int n,*L[NMAX],S[NMAX],ns,nl,C[NMAX],Q[NMAX];
bool viz[NMAX];
void citire()
{
FILE *fin=fopen("ciclueuler.in","r");
int m,i;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=n;++i)
{ L[i]=(int*)realloc(L[i],sizeof(int)); L[i][0]=0;}
while (m--)
{ int x,y;
fscanf(fin,"%d %d",&x,&y);
++L[x][0];
L[x]=(int*)realloc(L[x],(L[x][0]+1)*sizeof(int));
L[x][L[x][0]]=y;
++L[y][0];
L[y]=(int*)realloc(L[y],(L[y][0]+1)*sizeof(int));
L[y][L[y][0]]=x;
}
fclose(fin);
}
int eulerian()
{
int i;
for (i=1;i<=n;++i)
if (L[i][0]%2) return 0;
return 1;
}
void sterge(int v, int w)
{
int poz=0,i;
for (i=1;i<=L[v][0]&&!poz;++i)
if (L[v][i]==w) poz=i;
for (i=poz;i<L[v][0];++i)
L[v][i]=L[v][i+1];
L[v][0]--;
poz=0;
for (i=1;i<=L[w][0]&&!poz;++i)
if (L[w][i]==v) poz=i;
for (i=poz;i<L[w][0];++i)
L[w][i]=L[w][i+1];
L[w][0]--;
}
void euler(int v)
{
while (L[v][0])
{
int w=L[v][1];
S[++ns]=v;
sterge(v,w);
v=w;
}
}
int ver()
{
int v=eulerian();
if (!v) return 0;
ns=nl=0;
do
{
euler(v);
v=S[ns--];
C[++nl]=v;
}
while (ns);
return 1;
}
void afisare(int sol)
{
FILE *fout=fopen("ciclueuler.out","w");
if (!sol) fprintf(fout,"-1\n");
else { int i;
for (i=nl;i;--i)
fprintf(fout,"%d ",C[i]);
}
fclose(fout);
}
int main()
{
citire();
afisare(ver());
return 0;
}