Cod sursa(job #336825)

Utilizator josephsmateiJosephs Matei josephsmatei Data 1 august 2009 17:40:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <cstring>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    long int N, M;
    long int a, b, i, *grad;
    vector<long int>* vecini;
    queue<long int> coada;

    scanf("%ld %ld", &N, &M);
    vecini = new vector<long int> [N];
    grad = new long int[N];
    memset(grad, 0, sizeof(long int) * N);

    for (i = 0; i < M; ++i)
    {
	scanf("%ld %ld", &a, &b);
	vecini[a - 1].push_back(b - 1);
	grad[b - 1]++;
    }

    for (i = 0; i < N; ++i)
    {
	if(grad[i] == 0) coada.push(i);
    }
    coada.size();
    while(!coada.empty())
    {
	i = coada.front();
	printf("%ld ", i+1);
	for (int j = 0, length = vecini[i].size(); j < length; ++j)
	{
	    if ((--grad[vecini[i][j]]) == 0)
		coada.push(vecini[i][j]);
	}
	coada.pop();
    }

    return 0;
}