Cod sursa(job #2537697)

Utilizator thinkphpAdrian Statescu thinkphp Data 3 februarie 2020 21:34:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 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) {
             

           //for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it ) {
           for(int i = 0; i < G[node].size(); ++i) {

               if(!seen[G[node][i]]) {
                  seen[G[node][i]] = 1;        
               	  DFS(G[node][i]);
               } 
           }  

           sol[++sol[0]] = node;
      }

      void topsort() {

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

               if( !seen[i] ) {
                   seen[i] = 1;        
               	   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;
}