Cod sursa(job #490053)

Utilizator RegeleUmbrelorPopescu Mihai RegeleUmbrelor Data 4 octombrie 2010 20:05:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
using namespace std;
#include<stdio.h>
#include<vector>
const int N=50001, M=100001;
vector<int> v[N];
bool afisat[N];
int n,m, nr[N],af[N];

void citire()
{
	int x,y;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	scanf("%d%d",&n,&m);
	for(;m>0;--m)
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		nr[y]++;
	}
}

void bfs(int x)
{
	int p=0,u=0;
	af[u++]=x;
	while(u!=p)
	{
		x = af[p++];
		printf("%d ",x);
		afisat[x] = true;
		for(int i=0;i<v[x].size();++i)
		{
			nr[v[x][i]]--;
			if(!nr[v[x][i]])
			{
				af[u++]=v[x][i];
			}
		}
	}
}

int main()
{
	int i;
	citire();
	for(i=1;i<=n;++i)
		if(!afisat[i] && nr[i]==0)
			bfs(i);
	return 0;
}