Cod sursa(job #700938)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 1 martie 2012 12:39:18
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
typedef struct nod{int val;
                   nod *next;
};
int n,i,j,a,b,m,ic,sc,grad[10001],cd[50001];
nod *q,*v[50001];
int main()
{   fin >> n >> m;
	for(i=1;i<=m;++i)
	{   fin >> a >> b;
	    q = new nod;
		q -> val = b;
		q -> next = v[a];
		v[a] = q;
	    ++grad[b];
	}
	for(i=1;i<=n;++i)
		if(grad[i]==0)
			cd[++sc]=i;
	while(ic<sc)
	{   ++ic;
		fout << cd[ic] << " ";
		q = v[cd[ic]];
		while (q)
		{   --grad[q->val];
			if (!grad[q->val])
				cd[++sc]=q -> val;
			q = q->next;
		}
	}
	
	return 0;
}