Cod sursa(job #2931367)

Utilizator namesurname01Name Surname namesurname01 Data 31 octombrie 2022 00:03:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <deque>

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");


#define VERTECES 50001
vector<int> graph[VERTECES];
deque<int> deq;
int deg[VERTECES];

void topo() {
	while (!deq.empty()) {
		int node = deq.front();
		deq.pop_front();
		while (graph[node].size() > 0) {
			int neigh = graph[node].back();
			graph[node].pop_back();	//delete de arc between node and neigh
			deg[neigh]--;
			if (deg[neigh] == 0) {
				g << neigh << " ";
				deq.push_back(neigh);
			}
		}
	}
}

int main()
{
	int vertices, edges;
	f >> vertices >> edges;
	int x, y;
	for (int i = 1; i <= edges; ++i) {
		f >> x >> y;
		graph[x].push_back(y);
		++deg[y];
	}
	for (int i = 1; i <= vertices; ++i) {
		if (deg[i] == 0) {
			deq.push_back(i);
			g << i << " ";
		}
	}

	topo();

	

	f.close();
	g.close();
	return 0;
}