Cod sursa(job #2537726)

Utilizator thinkphpAdrian Statescu thinkphp Data 3 februarie 2020 21:54:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
	#include <iostream>
#include <vector>
#define FIN "sortaret.in"
#define FOUT "sortaret.out"
#define SIZE 50001
 
using namespace std;
 
class Graph {
 
	  private: 
	  vector<int> G[ SIZE ]; 
	  vector<int> seen;	
	  int nodes;
      int sol[SIZE];
 
      public:
      Graph(int numNodes) {
 
            seen.resize(numNodes + 1, 0);  
 
            nodes = numNodes;            
      }
 
      void addEdge(int x, int y){
 
           G[x].push_back(y);
      }
 
      void DFS(int node) {
             
           seen[node] = 1;        

           for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it ) {
           
               if(!seen[*it]) {

                  seen[*it] = 1;        

               	  DFS(*it);
               } 
           }  
 
           sol[++sol[0]] = node;
      }
 
      void topsort() {
 
           for(int i = 1; i <= nodes; ++i) {
 
               if( !seen[i] ) {
                  
               	   DFS(i); 
               }
           }
           freopen(FOUT, "w", stdout);
           for(int i = sol[0]; i > 0; --i) printf("%d ", sol[i]);
      }
 
};
 
int main(int argc, char const *argv[])
{
	int nodes, edges, x, y;
	freopen(FIN, "r", stdin);
 
	scanf("%d %d", &nodes, &edges);
    Graph G(nodes);
 
	while(edges--) {
		scanf("%d %d", &x, &y);
		G.addEdge(x, y);
	}
 
	G.topsort();
 
	return 0;
}