Cod sursa(job #2432663)

Utilizator alex.livadaruLivadaru Alexandru alex.livadaru Data 24 iunie 2019 17:22:12
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
	
#include <vector>
	
#include <list>
	
#include <iterator>
	
#define nmax 50001
	
 
	
using namespace std;
	
 
	
ifstream f("sortaret.in");
	
ofstream g("sortaret.out");
	
 
	
 
	
class graf{
	
private:
	
	vector<int> edges[nmax];
	
	vector<bool> visited;
	
	vector<int> tdesc;	
	
	int contor=0;
	
	int nodes;
	
public:
	
	vector<int> order;
	
	graf(int n){
	
	 visited.resize(n+1,0);
	
	 tdesc.resize(n+1,0);
	
	 nodes=n;
	
	}
	
	void addedge(int x, int y){
	
		edges[x].push_back(y);
	
	}
	
	void dfs(int nod){
	
         int i;
	
         for(i=0;i<edges[nod].size();i++){
	
         	 if(visited[edges[nod][i]]==0){
	
         	 	visited[edges[nod][i]]=1;
	
         	 	contor++;
	
         	 	dfs(edges[nod][i]);
	
         	 }
	
         }
	
      tdesc[nod]=contor;
	
      order.push_back(nod);
	
	}
	
	void topsort(){
	
          int i;
	
          for(i=1;i<=nodes;i++){
	
          	if(visited[i]==0){
	
          		visited[i]=1;
	
          		dfs(i);
	
          	}
	
          }
	
 			for(i=order.size()-1;i>=0;i--)
	
 				g<<order[i]<<" ";
	
	}
	
 
	
};
	
int main(){
	
	int n, m, x, y, i;
	
	f>>n>>m;
	
	graf graph(n);
	
	for(i=0;i<m;i++){
	
		f>>x>>y;
	
		graph.addedge(x,y);
	
	}
	
	graph.topsort();
	
 
	
}