Pagini recente » Cod sursa (job #2866776) | Cod sursa (job #2325934) | Cod sursa (job #2245860) | Cod sursa (job #767631) | Cod sursa (job #1746224)
#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);
}