Cod sursa(job #1260805)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 11 noiembrie 2014 16:47:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

const int nmax = 50000;
int n, m, coada[nmax], nrparinti[nmax], cateamafisat, l = 1, beg;
bool afisat[nmax];

vector<int> v[nmax];

int main(){
	int player_unu=0;

	in>>n>>m;
	for(int i = 0; i<m; i++)
	{
		int x, y;
		in>>x>>y;
		v[x].push_back(y);
		nrparinti[y]++;
	}

	for(int i = 1; i<=n; i++)
	{
		if(nrparinti[i]==0)
		{
			coada[l] = i;
			l++;
		}
	}

	while(cateamafisat!=n)
	{
		beg++;
		out<<coada[beg]<<' ';
		cateamafisat++;

		for(int i = 0; i<(int)v[coada[beg]].size(); i++)
		{
			nrparinti[v[coada[beg]][i]]--;
			if(nrparinti[v[coada[beg]][i]]==0)
			{
				coada[l] = v[coada[beg]][i];
				l++;
			}
		}
	}

	return player_unu;
}