Cod sursa(job #2432288)

Utilizator lucian2015blaugranadevil lucian2015 Data 22 iunie 2019 21:18:20
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 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();

}