Cod sursa(job #1463692)

Utilizator Tester01tester Tester01 Data 21 iulie 2015 15:12:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
using namespace std; 
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
#define Nmax 100013
 
class cell {
  public : 
 	int node;
 	cell *prev;
 	cell (int a, cell *l) {node=a; prev=l;};
 };
 	  
 class UndirectedGraph {
 	 private : 
 	          cell *adj[Nmax];
 	          bool used[Nmax];
 	          
 	 public : 
	          vector <int> TopSort;
	          
	          void dfs(int node){
 	          	for (cell *it = adj[node];it;it=it->prev){
 	          	   if (!used[it->node]) dfs(it->node);
                   used[it->node]=1;
                  }
 	              TopSort.push_back(node);
 	          	 }
 	          	 
 		      void addEdge(int a,int b){
 		      	 cell *aux = new cell(b,adj[a]); adj[a]=aux;
 		      }
 		      
 		      void topologicalSort(int n){
 		      	for (int i=1;i<=n;++i)
 		      	  if (!used[i]) {
					   dfs(i);
					   used[i]=1;
				    }
 		      	}
 } Graph;
 
int n,m,a,b;
int main(void) {
 cin>>n>>m;
 while(m--) {
 	cin>>a>>b;
 	Graph.addEdge(a,b);
    }
 Graph.topologicalSort(n);
 for (int i=Graph.TopSort.size()-1;i>=0;--i) 
  cout<<Graph.TopSort[i]<<" ";
 return 0;
}