topological sort, C++ (gcc)

topological sort

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph{
public:
	Graph(int n){
		number_of_nodes=n;
		edges.resize(n,vector<int>());
		indegree.resize(n,0);
	}
	void add_edge(int u, int v){
		edges[u].push_back(v);
		indegree[v]++;
	}
	vector<int> topological_sort(){
		vector<int> result;
		vector<int> in=indegree;
		queue<int> Q;
		for(int i=0;i<number_of_nodes;i++){
			if(in[i]==0) Q.push(i); 
		}
		while(!Q.empty()){
			int v=Q.front();
			result.push_back(v);
			Q.pop();
			for(vector<int>::iterator e=edges[v].begin();e!=edges[v].end();e++){
				in[*e]--;
				if(in[*e]==0) Q.push(*e);
			}
		}
		if(result.size()!=number_of_nodes) result.clear();
		return result;
	}
private:
	int number_of_nodes;
	vector<vector<int> > edges;
	vector<int> indegree;
};

int main(){
	Graph g(5);
	g.add_edge(0,1); // 1 depends on 0 
	g.add_edge(4,2);
	g.add_edge(1,3);
	g.add_edge(1,4);
	g.add_edge(4,3);
	vector<int> order=g.topological_sort();
	if(order.empty()) cout<<"Can not reconstruct lost blocks!"<<endl;
	else{
		for(vector<int>::iterator v=order.begin();v!=order.end();v++){
			cout<<*v<<" ";
		}
		cout<<endl;
	}
	return 0;
}


run \| edit \| history \| help	0