Pagini recente » Cod sursa (job #574321) | Cod sursa (job #98364) | Cod sursa (job #600253) | Cod sursa (job #2388364) | Cod sursa (job #614222)
Cod sursa(job #614222)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct nod
{
int ascend;
nod *next;
};
int N,precedenti[50012],vizitat[50012];
nod *ASC[50012];
nod *CAP;
void citeste_fisier();
void parcurgere();
bool verif_term();
nod *constructie(int info);
void insert_nod(nod *&cap,int dest);
void descreste_el(int el);
void filtreaza(FILE *g);
void remove_nod(nod *&cap,int info);
int main()
{
citeste_fisier();
parcurgere();
return 0;
}
void parcurgere()
{
FILE *g = fopen("sortaret.out","w");
int i,j;
for(i=0;i<N;i++)
{
if ( precedenti[i] == 0 && vizitat[i] == 0 )
{
vizitat[i] = 1;
fprintf(g,"%d ",i+1);
descreste_el(i);
}
else
if ( precedenti[i] > 0 )
{
insert_nod(CAP,i);
}
}
filtreaza(g);
fclose(g);
}
void filtreaza(FILE *g)
{
nod *p = CAP;
while ( CAP != 0 )
{
if ( precedenti[p->ascend] == 0 && vizitat[p->ascend] == 0 )
{
vizitat[p->ascend] = 1;
fprintf(g,"%d ",p->ascend+1);
descreste_el(p->ascend);
remove_nod(CAP,p->ascend);
}
p = p->next;
if ( p == 0 )
p = CAP;
}
}
void remove_nod(nod *&cap,int info)
{
nod *p = cap,*p1 = 0;
while ( p != 0 )
{
if ( p->ascend == info )
{
if ( p1 == 0 )
{
cap = cap->next;
free(p);
return;
}
p1->next = p->next;
free(p);
return;
}
p1 = p;
p = p->next;
}
}
void descreste_el(int el)
{
nod *p = ASC[el];
while ( p != 0 )
{
precedenti[p->ascend]--;
p = p->next;
}
}
bool verif_term()
{
for(int i=0;i<N;i++)
if ( vizitat[i] == 0 )
return false;
return true;
}
void citeste_fisier()
{
FILE *f = fopen("sortaret.in","r");
if ( f == 0 )
return;
int M,a,b;
fscanf(f,"%d %d",&N,&M);
for(int i=0;i<M;i++)
{
fscanf(f,"%d %d",&a,&b);
precedenti[b]++;
insert_nod(ASC[a],b);
//adiac[a][b] = 1;
}
fclose(f);
}
void insert_nod(nod *&cap,int dest)
{
nod *p = cap;
nod *c = constructie(dest);
if ( p == 0 )
{
cap = c;
return;
}
cap = c;
cap->next = p;
}
nod *constructie(int info)
{
nod *p = (nod *)malloc(sizeof(nod));
p->ascend = info;
p->next = 0;
return p;
}