Cod sursa(job #1611118)

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

using namespace std;

vector <int> results;


void backt(vector<vector <int> >& arcs, vector<int>& degs, int current)
{
	int i;
	results.push_back(current);
	for(i=0; i<arcs[current].size(); ++i)
	{
		--degs[arcs[current][i]];
		if(!degs[arcs[current][i]])
		{
			--degs[arcs[current][i]];
			backt(arcs, degs, arcs[current][i]);
		}
	}
}

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

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

    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])
			backt(arcs, degs, i);

	for(i=0; i<n; ++i)
		printf("%d ", results[i]);
	printf("\n");
    return 0;
}