Cod sursa(job #2469695)

Utilizator gazdac_alex@yahoo.comGazdac Alexandru Eugen [email protected] Data 7 octombrie 2019 21:09:53
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

int const maxim = 50005;
int n, m, tata;
int distanta[maxim] = {0};
vector<int> stocare[maxim];
queue<int> coada;

void citire() {
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		in >> a >> b;
		stocare[a].push_back(b);
		distanta[b] = a;
	}
}

void bfs() {
	int nod, vecin;
	while (!coada.empty()) {
		nod = coada.front();
		coada.pop();
		out << nod << " ";
		for (size_t i = 0; i < stocare[nod].size(); i++) {
			vecin = stocare[nod][i];
			if (distanta[vecin] == -1) {
				distanta[vecin] = distanta[nod] + 1;
				coada.push(vecin);
			}
		}
	}
}

int main() {
	citire();
	for (int i = 1; i <= n; i++) {
		if (distanta[i] == 0)tata = i;
		distanta[i] = -1;
	}
	distanta[tata] = 1;
	coada.push(tata);
	bfs();
	return 0;
}