Cod sursa(job #2041684)

Utilizator Spiromanii_MessiUNIBUCThrowTerror Spiromanii_Messi Data 17 octombrie 2017 18:08:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std ;

ifstream fin ("sortaret.in") ;
ofstream fout ("sortaret.out") ;

int main(int argc, char const *argv[])
{
	int n, m ; 
	fin >> n >> m ; 
	vector <int> grad (n + 1, 0) ; 
	std::vector< vector <int> > gr (n + 1); // keep the graph
	while (m --) {
		int x, y ; // edge x -> y ;
		fin >> x >> y ; 
		gr [x].push_back (y) ; 
		grad [y] += 1 ; // increase the number of incident edges in y
	}
	queue <int> Q ; 
	for (int i = 1 ; i <= n ; ++ i) {
		if (grad [i] == 0) {
			Q.push (i) ; 
		}
	}
	while (!Q.empty()) {
		auto nod = Q.front() ; 
		Q.pop () ;
		for (auto &neigh : gr [nod]) {
			-- grad [neigh] ;
			if (grad [neigh] == 0) Q.push (neigh) ; 
 		}
 		fout << nod << ' ' ; 
	}
	return 0;
}