Cod sursa(job #1611061)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 23 februarie 2016 22:16:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

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

    int x, y, i, j, n, m;
    scanf("%d%d", &n, &m);
    vector< vector<int> > arcs (n+1);
    vector<int> degs (n+1, 0);
    queue<int> q;

    for(i=1; i<=m; ++i)
	{
		scanf("%d%d", &x, &y);
		arcs[x].push_back(y);
		++degs[y];
	}

    for(i=1; i<=n; ++i)
		if(!degs[i])
			q.push(i);

	while(!q.empty()) {
		int current = q.front();
		q.pop();
		printf("%d ", current);
		for(i=0; i<arcs[current].size(); ++i) {
			--degs[arcs[current][i]];
			if(!degs[arcs[current][i]])
				q.push(arcs[current][i]);
		}
	}

	printf("\n");
    return 0;
}