Cod sursa(job #343284)

Utilizator bog29Antohi Bogdan bog29 Data 25 august 2009 13:45:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream>
#include<vector>
#define dmax 50003
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int n,m,gi[dmax],tot,st[dmax],crt;
vector<int>g[dmax];
int main()
{	int i,a,b;
	vector<int>::iterator it;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b;
		g[a].push_back(b);
		gi[b]++;
	}
	in.close();
	while(tot<n)
	{	for(i=1;i<=n;i++)
		{	if(gi[i]==0)
			{	crt++;
				tot++;
				st[crt]=i;
				for(it=g[i].begin();it<g[i].end();it++)
					gi[*it]--;
				gi[i]=-1;
			}	
		}	
	}
	for(i=1;i<=n;i++)
		out<<st[i]<<" ";
	out.close();
	return 0;
}