Cod sursa(job #2611256)

Utilizator alex.ivan1105Ivan Alexandru alex.ivan1105 Data 6 mai 2020 16:43:34
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 50009

class Task {
public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

private:
    int n, m;

    vector<int> adj[NMAX];

    /* 
        Diferenta fata de DFS este ca retin un vector in care voi introduce fiecare nod DUPA ce il termin de parcurs.
        La finalul parcurgerii DFS il inversez pentru a avea ordinea corecta a nodurilor in functie de timpii de iesire. 
    */
    vector<int> topsort;

    void read_input() {
        ifstream fin("sortaret.in");
        fin >> n >> m;

        for (int i = 1; i <= m; ++i) {
            int x, y;

            fin >> x >> y;

            adj[x].push_back(y);
            // adj[y].push_back(x);
        }

        fin.close();
    }

    void print_output() {
        ofstream fout("sortaret.out");
        for (auto &it : topsort) {
            fout << it << " ";
        }
        fout << endl;
        fout.close();
    }

    void get_result() {
       do_dfs();
    }

    void do_dfs() {
        vector<int> used(n + 1, 0);
    
        for (int i = 1; i <= n; ++i) {
            if (!used[i]) {
                dfs(i, used, topsort);
            }
        }

        reverse(topsort.begin(), topsort.end());
    }

    void dfs(int& node, vector<int>& used, vector<int> &topsort) {
        used[node] = 1;

        for (auto& it : adj[node]) {
            if (!used[it]) {
                dfs(it, used, topsort);
            }
        }

        // Introduc nodul in vector dupa ce am termiant vizitarea sa (am parcurs toti vecinii sai)
        topsort.push_back(node);
    }
};

int main() {
    // daca las linia asta citesc din fisier
    // assert(freopen("dfs.in",  "r", stdin)); 

    // daca las linia asta afisez in fisier
    // assert(freopen("dfs.out", "w", stdout));

    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}