Cod sursa(job #917382)

Utilizator Gabriela19091993Busca Gabriela Gabriela19091993 Data 17 martie 2013 19:26:14
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<queue>

using namespace std;

vector <int> g[10001];
int grad[10001];
queue <int> q;

int main()
{
	int m, n, i, a, b,x;
	ifstream f("sortaret.txt");
	f>>n;
	f>>m;
	for(i=0;i<m;i++)
	{
		f>>a>>b;
		g[a].push_back(b);
		grad[b]++;
	}
	
	for(i=1;i<=n;i++)
		if(grad[i]==0)
			q.push(i);

	for(i=1;i<=n;i++)
	{
		x=q.front();
		for (unsigned j=0; j < g[x].size(); j++) 
		{
			grad[g[x][j]]--;
			if(grad[g[x][j]]==0)
				q.push(g[x][j]);
		}
		cout<<q.front()<<" ";
		q.pop();
	}
	return 0;
}