Cod sursa(job #1089402)

Utilizator cricriFMI - Radu Vlad cricri Data 21 ianuarie 2014 18:09:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
using namespace std;

#include<fstream>
#include<iostream>
#include<vector>


ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector<int> a[100001];
vector<int> queue;

int visited[50001], degree[50001];

int n,m;

int main()
{
	int i, j , x, y;
	
	f>>n>>m;

	for(i = 0;i<m;i++)
	{
		f>>x>>y;
		a[x].push_back(y);
		degree[y]++;
	}

	for(i = 1;i<=n;i++)
	{
		if(degree[i] == 0)
			queue.push_back(i);
	}


	for(i=0;i<n;i++)
	{
		for(j=0;j<a[queue[i]].size();j++)
		{
			degree[a[queue[i]][j]]--;
			if(degree[a[queue[i]][j]] == 0)
				queue.push_back(a[queue[i]][j]);
		}
	}

	for(i=0;i<n;i++)
		g<<queue[i]<<' ';

	//system("pause");

	return 0;
}