Cod sursa(job #1822992)

Utilizator AetheryonStefan Bereghici Aetheryon Data 5 decembrie 2016 19:43:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#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;
}