Cod sursa(job #1746224)

Utilizator florinpocolPocol Florin florinpocol Data 22 august 2016 21:50:56
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.85 kb
#include <stdio.h>

#define ALB 0;
#define GRI 1;
#define NEGRU 2;

int n;

typedef struct node
   {
        int vf;
        struct node *next;
   }  *PNOD;


PNOD *L;//Listele de vecini pentru fiecare nod
PNOD adresa; // lista simplu inlantuita
int *culoare;
//int color[NMAX];


void add(int v1, int v2)
{
    PNOD nou;
    nou=(PNOD)calloc(1,sizeof(PNOD));
    nou->vf=v2;
    nou->next=L[v1];
    L[v1]=nou;

}

void citire()
{

    int  m;

    freopen("sortaret.in","r",stdin);

    scanf("%d %d",&n,&m);


    L=(PNOD*)calloc(n+1,sizeof(PNOD));

    while (m>0)
    {
        int v1,v2;
        scanf("%d %d",&v1,&v2);
        add(v1,v2);
        m--;
    }


/*
Afisare lista de vecini
    int i;
    for (i=1; i<=n; i++)
        {
            printf("%d: ",i);
            PNOD p=L[i];
            while (p)
               {
                   printf("%d ",p->vf);
                   p=p->next;
               }
            printf("\n");
        }
*/

}


void push(int vf)
{
    PNOD nou;
    nou=calloc(1,sizeof(PNOD));
    nou->vf=vf;
    nou->next=adresa;
    adresa=nou;
}


void DFS(int vf)
{
    culoare[vf]=GRI;
    PNOD p;
    p=L[vf];


    while (p)
    {
        if (culoare[p->vf]==0)
        {
             DFS(p->vf);
        }
        p=p->next;
    }

    culoare[vf]=NEGRU;
    push(vf);
}

void Sortare_Topologica()
{
    culoare= (int*)calloc(n+1,sizeof(int));
    int i;



    for (i=1; i<=n; i++)
    {
        if (culoare[i]== 0 )
              DFS(i);
    }

}



void afisare()
{
     freopen("sortaret.out","w",stdout);

     PNOD p;
     p=adresa;
     while (p)
     {
         printf("%d ",p->vf);
         p=p->next;
     }
}


int main()
{
    citire();
    Sortare_Topologica();
    afisare();
    return(0);
}