Cod sursa(job #1808085)

Utilizator mateinMatei Nistor Ionut matein Data 17 noiembrie 2016 12:16:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Node {
public:
	int number_node_in;
	std::vector<int> node_out;
	Node() {
		number_node_in = 0;
	}
};

class la_comparison
{
public:
	bool operator() (const int& lhs, const int& rhs) {
		return lhs > rhs;
	}	
};

int main() {
	int n, m, x, y;
	ifstream in;
	ofstream out;
	in.open("sortaret.in");
	out.open("sortaret.out");
	in >> n >> m;
	std::vector<Node> graph(n + 1);
	std::priority_queue<int, std::vector<int>, la_comparison> mypq;
	//std::vector<int> check(n + 1, 0);
	for(int i = 0; i < m; i++) {
		in>>x>>y;
		graph[x].node_out.push_back(y);
		graph[y].number_node_in++;
	}

	for(int i = 1; i <= n; i++) {
		if(!graph[i].number_node_in) {
			mypq.push(i);
			//check[i] = 1;
		}
	}
	int ind, curr_ind;

	while(!mypq.empty()) {

		ind = mypq.top();
		mypq.pop();
		for(int i = 0; i < graph[ind].node_out.size(); i++) {

			curr_ind = graph[ind].node_out[i];
			graph[curr_ind].number_node_in--;
			if(!graph[curr_ind].number_node_in) {
				mypq.push(curr_ind);
			}

		}
		out<< ind <<' ';
	}



	/*for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cout<<graph[i][j]<<' ';
		}
		cout<<'\n';
	}*/

}