Pagini recente » Cod sursa (job #2740790) | Cod sursa (job #1335658) | Cod sursa (job #1784703) | Cod sursa (job #544739) | Cod sursa (job #1822992)
#include <bits/stdc++.h>
using namespace std;
#define Nmax 50001
FILE *in ,*out;
class DirectedGraph {
private :
int nodes;
vector <int> adjList[Nmax];
bool used[Nmax];
vector <int> sortedNodes;
void dfs(int parent){
used[parent] = true;
for (int i=0;i<adjList[parent].size();++i){
if (!used[adjList[parent][i]]){
dfs(adjList[parent][i]);
}
}
sortedNodes.push_back(parent);
}
public :
DirectedGraph(int n){
this->nodes = n;
memset(used,0,sizeof used);
}
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);
}
}
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;
}