Cod sursa(job #902569)

Utilizator SerbanAlexandru9Serban Alexandru SerbanAlexandru9 Data 1 martie 2013 15:09:05
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <stdio.h>
#include<vector>

using namespace std;

vector <int> l[100001];
int n,m,c[100001],nr;


void cit()
{   int a,b;
    freopen("ciclueuler.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        l[a].push_back(b);
    }
    fclose(stdin);
}
void ciclu(int c[100001],int &nr,int k)
{
    int  h=0;
    nr=1;
    h=k;
    c[nr]=h;
    do
    {   nr++;
        c[nr]=l[h][0];
        l[h].erase(l[h].begin());
        h=c[nr];
    }while(h!=k);
}
void combina(int c[100001],int c1[100001],int &dc,int dc1,int k)
{
    int dx=0;
    int x[100001];
    for(int i=1;i<=k;i++)
    {
        dx++;
        x[dx]=c[i];
    }
    for(int i=2;i<=dc1;i++)
    {
        dx++;
        x[dx]=c1[i];
    }
    for(int i=k+1;i<=dc;i++)
    {
        dx++;
        x[dx]=c[i];
    }
    for(int i=1;i<=dx;i++)
        c[i]=x[i];
    dc=dx;
}
void rezolva()
{
    int h=-1,c1[100001],u=0,i;
    ciclu(c,nr,1);
    while(h!=0)
    {   h=0;
        for(i=1;i<=nr;i++)
            if(l[c[i]].size()>0)
        {
            h=c[i];



            ciclu(c1,u,h);
            combina(c,c1,nr,u,i);
            break;
        }
    }
}
void afis()
{
    freopen("ciclueuler.out","w",stdout);
    for(int i=1;i<=nr;i++)
        printf("%d ",c[i]);
    fclose(stdout);
}
int main()
{   cit();
    rezolva();
    afis();
    return 0;
}