Cod sursa(job #1007969)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 9 octombrie 2013 22:28:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <vector>
using namespace std;

vector <int> v[50002];
int res[50002],rp,rit;
int ins[50002];
int n,m;

int main() {
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		v[a].push_back(b);
		ins[b]++;
	}
	for (int i=1;i<=n;i++) {
		if (ins[i] == 0) res[++rp] = i;
	}
	for (int i=1;i<=n;i++) {
		int crt = res[i];
		while (!v[crt].empty()) {
			int nod = v[crt].back(); v[crt].pop_back();
			ins[nod]--;
			if (ins[nod] == 0) res[++rp] = nod;
		}
	}
	for (int i=1;i<=n;i++) printf("%d ",res[i]);
	return 0;
}