Cod sursa(job #612361)

Utilizator sergiupPopescu Sergiu sergiup Data 7 septembrie 2011 01:17:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#include <vector>

using namespace std;

vector<int> g[50005];
int n,m;

int q[50005];
int deg[50005];
int qp = 1;

void topologic(){
	for (int i = 1 ; i <= n ; ++i){
		if (deg[i] == 0)
			q[qp++] = i;
	}

	for (int i = 1 ; i <= n ; ++i){
		for (int j = 0 ; j < g[q[i]].size();++j){
			if (--deg[g[q[i]][j]] == 0){
				q[qp++] = g[q[i]][j];
			}
		}
		printf("%d ",q[i]);
	}
}

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);

	scanf("%d%d",&n,&m);

	for (int i = 0 ; i < m ; ++i){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		deg[y]++;
	}
	topologic();
	return 0;
}