Cod sursa(job #2410104)

Utilizator SmokeCiocotisan Cosmin Smoke Data 19 aprilie 2019 18:45:19
Problema Sortare topologica Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

#define NMAX 5000
using namespace std;
int N, M;
int  gr_int[NMAX];

deque<int> coada;
vector<int > G[NMAX];

void citire()
{

	ifstream in("sortaret.in");

	in >> N >> M;
	int x, y;

	for (int i = 0; i < M; i++)
	{
		in >> x >> y;
		G[x].push_back(y);
		gr_int[y]++;

	}

	in.close();


}

void solve_prob()
{

	for (int i = 1; i <= N; i++)
		if (gr_int[i] == 0) coada.push_back(i);

	vector <int> ::iterator it;

	for (int i = 0; i < N; i++)
	{
		int x = coada[i];

		for (it = G[x].begin(); it < G[x].end(); it++)
		{
			gr_int[*it]--;

			if (gr_int[*it] == 0) coada.push_back(*it);


		}


	}



}


void afisare()
{
	ofstream out("sortaret.out");


	for (int i = 0; i < N; i++)
		out << coada[i] << " ";




}



int main(void)
{
	citire();
	solve_prob();
	afisare();



}