Cod sursa(job #443535)

Utilizator IlieeUngureanu Ilie Iliee Data 17 aprilie 2010 13:21:13
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
#include<vector>
using namespace std;
void read(), solve();
int n,m,a,b,i,r,x[50010],g[50010];
vector<int> v[50010];
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		g[b]++;
	}
}
void solve()
{
	vector<int>::iterator it;
	for(i=1;i<=n;i++)
		if(!g[i])
			x[++r]=i;
	for(i=1;i<=r;i++)
		for(it=v[i].begin();it!=v[i].end();it++)
		{
			g[*it]--;
			if(!g[*it])
				x[++r]=*it;
		}
	for(i=1;i<=n;i++)
		printf("%d ",x[i]);
}