Cod sursa(job #2668602)

Utilizator tudoranita112Tudor Anita tudoranita112 Data 5 noiembrie 2020 03:47:12
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

#define MAXN 50100
#define pb push_back

int V, E, grad_ext[MAXN], que[MAXN]; vector<int> nodes[MAXN];

// grad_ext[x] = gradul exterior al nodului x
// coada que folosita pt a pune nodurile cu grad_ext 0

void solve(void)
{
	int i, x; vector<int>::iterator it;

	for (x = 1; x <= V; x++)
		if (grad_ext[x] == 0)
		{
			que[++que[0]] = x;
		}
	for (i = 1; i <= V; i++)
	{
		x = que[i];
		for (it = nodes[x].begin(); it != nodes[x].end(); ++it)
		{
			grad_ext[*it]--;
			if (grad_ext[*it] == 0)
			{
				que[++que[0]] = *it;
			}
		}
	}
}

void read_data(void)
{
	int i, a, b;
	ifstream sortaret_in;
	sortaret_in.open("sortaret.in");

	sortaret_in >> V >> E;
	for (i = 1; i <= E; i++)
	{
		sortaret_in >> a >> b;
		nodes[a].pb(b);
		grad_ext[b]++;
	}
}

void sortare_topologica()
{
	int i;
	ofstream sortaret_out;
	sortaret_out.open("sortaret.out");

	for (i = 1; i <= V; i++)
		sortaret_out << que[i]<<" ";
}

int main(void)
{
	
	
	
	read_data();
	solve();
	sortare_topologica();

	return 0;
}