Pagini recente » Rating Marius Darius (labmoisil30) | Istoria paginii utilizator/dumitru_george | Profil motty | Paranteze | Cod sursa (job #1822969)
#include <bits/stdc++.h>
using namespace std;
#define Nmax 50013
FILE *in ,*out;
class DirectedGraph {
private :
int nodes;
vector <int> adjList[Nmax];
bool used[Nmax];
vector <int> sortedNodes;
void dfs(int parent){
for (int i=0;i<adjList[parent].size();++i){
if (!used[adjList[parent][i]]){
dfs(adjList[parent][i]);
used[adjList[parent][i]]=1;
}
}
sortedNodes.push_back(parent);
}
public :
DirectedGraph(int n){
this->nodes = n;
}
void addEdge(int from,int to){
adjList[from].push_back(to);
}
void topologicalSorting(){
for (int i=1;i<=nodes;++i){
if (!used[i]){
dfs(i);
used[i] = 1;
}
}
for (int i=sortedNodes.size()-1;i>=0;--i){
fprintf(out,"%d ",sortedNodes[i]);
}
}
};
int n,m,from,to;
int main(void){
in = fopen("sortaret.in","r");
out = fopen("sortaret.out","w");
fscanf(in,"%d%d",&n,&m);
DirectedGraph graph = DirectedGraph(n);
while(m--){
fscanf(in,"%d%d",&from,&to);
graph.addEdge(from,to);
}
graph.topologicalSorting();
return 0;
}