Cod sursa(job #2537843)

Utilizator thinkphpAdrian Statescu thinkphp Data 3 februarie 2020 23:55:27
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#define SIZE 50001
#define FIN "sortaret.in"
#define FOUT "sortaret.out"

using namespace std;

class Graph {
 
      public: 

      Graph(int nNodes) {

            adj = new list<int>[ nNodes + 1];

            seen.resize(nNodes + 1, 0);            
           
            nodes = nNodes;
      }

      vector<int> topsort() {

           for(int i = 1; i <= nodes; ++i) {

           	   if(!seen[i]) {

           	   	   DFS(i);
           	   }
           }   

           return sol;
      }

      void addEdge(int u, int v) {

           adj[u].push_back(v);
      }

      void DFS(int node) {

           seen[node] = 1;

           for(const auto&v: adj[node]) {

           	   if(!seen[v]) {

                  seen[v] = 1;

           	   	  DFS(v);
           	   }
           }

           sol.push_back(node);
      }      

      vector<int> getSol() {

      	   return sol; 
      }

      private:

      list<int> *adj;
      int nodes;
      vector<int> seen;
      vector<int> sol;
      	

};

int main(int argc, char const *argv[])
{ 
	int u,v, nodes, edges;

	freopen(FIN, "r", stdin);

	freopen(FOUT, "w", stdout);

	cin>>nodes>>edges;

	vector<int> sol; 
	
	Graph *g = new Graph(nodes);
 
	       while(edges--) { 

	          cin>>u>>v;

	          g->addEdge(u, v);	          
           }    

	       sol = g->topsort(); 
	       
	       for(vector<int>::reverse_iterator it = sol.rbegin(); it != sol.rend(); ++it) 

           cout<<*it<<" ";
	       

	return 0;
}