Cod sursa(job #1346534)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 18 februarie 2015 12:29:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include<vector>
#include<queue>

using namespace std;

int in[50002];
vector<int> out[50002];
queue<int> q;


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

	int n, m, i, j;

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

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

	while(q.empty()==false)
	{
		int x=q.front();
		q.pop();
		printf("%d ", x);

		for(i=0; i<out[x].size(); ++i)
		{
			if(in[out[x][i]]>0)
				--in[out[x][i]];
			if(in[out[x][i]]==0)
			{
				q.push(out[x][i]);
				in[out[x][i]]=-1;
			}
		}
	}

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