Cod sursa(job #2656585)

Utilizator robbie112Popescu Stefan robbie112 Data 8 octombrie 2020 02:09:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
/*
INFOARENA
Sortare Topologica
https://www.infoarena.ro/problema/sortaret
*/

#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n, m;
vector<vector<int> >L;
vector<int> d;

void read(const char *file_name) {
	ifstream f(file_name);
	f >> n >> m;
	L.resize(n + 1);
	d.resize(n + 1);
	int x, y;
	while (f >> x >> y)
	{
		L[x].push_back(y);
		d[y]++;
	}
	f.close();
}
int main() {
	queue<int>Q;
	vector<int>Sol;

	read("sortaret.in");

	for (int i = 1; i <= n; i++)
		if (d[i] == 0) Q.push(i);
	while(!Q.empty()){
		int x = Q.front();
		Q.pop();
		Sol.push_back(x);
		for (int y : L[x])
		{
			d[y]--;
			if (d[y] == 0) Q.push(y);
		}
	}
	ofstream g("sortaret.out");
	for (int x : Sol)
		g << x << " ";
	g.close();
	
	return 0;
}