Cod sursa(job #2423424)

Utilizator dadada876Cinca Adrian dadada876 Data 21 mai 2019 13:01:33
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int gradint[50005], viz[50005];
vector <int> graf[50005];
queue <int> noduri;
int main()
{
	int N, M;
	f >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y;
		f >> x >> y;
		gradint[y]++;
		graf[x].push_back(y);
	}
	for (int i = 1; i <= N; i++) 
		if (gradint[i] == 0) {
			noduri.push(i);
			viz[i] = 1;
		}

	
	while (noduri.empty() == false) {
		int nod = noduri.front();
		noduri.pop();
		g << nod << ' ';
		for (int i = 0; i < graf[nod].size(); i++) {
			int vecin = graf[nod][i];
			gradint[vecin]--;
		}
		graf[nod].clear();
		for (int i = 1; i <= N; i++) 
			if (gradint[i] == 0 && viz[i]==0) {
				noduri.push(i);
				viz[i] = 1;
			}
		
	}
	f.close();
	return 0;
}