Cod sursa(job #372546)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 10 decembrie 2009 19:10:36
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<fstream>
#include<cstdlib>
#define MAX 100000
using namespace std;
struct nod{int info;
        nod *next;};
int n,m,v[50004],timp,ordine[50005];
nod * a[50004];
FILE *fout=fopen("sortaret.out", "w");

void write()
{
    fprintf(fout,"%d %d\n", n, m);
    for(int i=1;i<=n;i++)
    {
        nod * p = a[i];
        fprintf(fout,"%d : ",i);
        while(p)
        {
            fprintf(fout,"%d ", p->info);
            p=p->next;
        }
        fprintf(fout,"\n");
    }

}

void read()
{
    FILE *fin=fopen("sortaret.in", "r");
    fscanf(fin,"%d %d",& n,& m);
    for(int i=1;i<=n;i++)
        a[i]=NULL; 
    while(m)
    {
        int i,j;
        fscanf( fin ,"%d %d", &i, &j);
        nod *p=new nod;
        p->info=j;
        p->next=a[i];
        a[i]=p;
        m--;
    }

}

void dfs(int varf)
{
    v[varf]=1;
    nod *p = a[varf];
    while(p)
    {
        if(v[p->info]==0)
        {
            dfs(p->info,nrc);
			timp++;
			ordine[timp]=varf;
        }
        p=p->next;
    }
}

void sterge(nod *p)
{
    nod *t=p;
    while(p)
    {
        t=p;
        p=p->next;
        delete t;
    }
}

int main()
{
    read();
    //write();
    int nrc=0;
    for(int i=1;i<=n;i++)
        if(v[i]==0)
            dfs(i)
	for(int i=n;i>=1;i--)
		fprintf( fout ,"%d " , ordine[i]);
		
    return 0;
}