Cod sursa(job #2130000)

Utilizator vlad.theodorVlad Theodor vlad.theodor Data 13 februarie 2018 12:54:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

void citire();
void desc();

int n, m;
int gint[50005], niv[50005];
vector< vector<int> > G;

int main()
{
	citire();
	desc();
	return 0;
}

void desc()
{
	int i, j, vecin;
	int nr = 0, nivel = 0;
	while (nr != n)
	{
		niv[0] = 0;
		for (i = 1; i <= n; i++)
			if (gint[i] == 0)
			{
				niv[++niv[0]] = i;
				gint[i] = -1;
				nr++;
			}

		for (i = 1; i <= niv[0]; i++)
		{
			vecin = niv[i];
			fout << vecin << ' ';
			for (j = 1; j <= G[vecin][0]; j++)
				gint[G[vecin][j]]--;
		}
	}
	fout << '\n';
}

void citire()
{
	int x, y, i;
	fin >> n >> m;

	vector<int> aux;
	aux.push_back(0);
	for (i = 0; i <= n; i++)
        G.push_back(aux);

	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		G[x][0]++;
		G[x].push_back(y);
		gint[y]++;
	}
}