Cod sursa(job #146049)

Utilizator uta_cristianUta Cristian uta_cristian Data 1 martie 2008 09:24:02
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
long mat[1000][1000],d[1000],n,m;
struct nod
{long inf;
 nod *leg;
}*p;
void creare(long x,nod *&p)
{nod *nou;
 nou=new nod;
 nou->inf=x;
 nou->leg=NULL;
  if (p==NULL) p=nou;
  else {nod *q;
        q=p;
        while (q->leg)
			q=q->leg;
        q->leg=nou;
       } 
}
void degree_init()
{long i,j;
  for (i=0;i<n;i++)
	  for (j=0;j<n;j++)
		  if (mat[i][j]) d[j]+=mat[i][j];
  for (i=0;i<n;i++)
	  if (d[i]==0) creare(i,p);
}
void sortare()
{long x;
 while (p!=NULL)
  {x=p->inf;
   g<<x+1<<" ";
   p=p->leg;
    for (long i=0;i<n;i++)
		if (mat[x][i]>0) {d[i]-=mat[x][i]; if (d[i]==0) creare(i,p);}
  }
}
void citire()
{f>>n>>m;
 long i,x,y;
  for (i=0;i<m;i++)
     {f>>x>>y;
      mat[x-1][y-1]++;
     }
}
int main()
{
citire();
degree_init();
sortare();
return 0;
}