Cod sursa(job #1212275)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 24 iulie 2014 11:57:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
using namespace std;
typedef struct nod{nod *urm;int val;} *NOD;
NOD v[50001];
int income[50001];
void addNodeFrom(NOD &q,int value)
{
	NOD p=new nod;
	p->val=value;
	p->urm=q;
	q=p;
}
int main()
{
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	int n,m,x,y,i,p=0,u=1;
	int tail[50001];
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		income[y]+=1;
		addNodeFrom(v[x],y);
	}
	for(i=1;i<=n;++i) if(income[i]==0) tail[++p]=i;
	while(u<=p)
	{
		for(NOD q=v[u];q;q=q->urm)
		{
			income[q->val]--;
			if(income[q->val]==0) tail[++p]=q->val;
		}
		++u;
	}
	for(i=1;i<=p;++i) g<<tail[i]<<" ";
	f.close();
	g.close();
	return 0;
}