Cod sursa(job #2610205)

Utilizator diana.megeleaDiana Megelea diana.megelea Data 4 mai 2020 17:14:00
Problema Sortare topologica Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 50001

 

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

  private:
    int n, m;
    vector<int> lista_vecini[NMAX];

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

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

            lista_vecini[x].push_back(y);
        }

        fin.close();
    }

    vector<int> get_result() {
        vector<bool> visited(n + 1, 0);
        vector<int> topsort;

        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                dfs(i, visited, topsort);
            }
        }

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

    void dfs(int i, vector<bool> &visited, vector<int> &topsort) {
        visited[i] = 1;

        for (auto vecin : lista_vecini[i]) {
            if (!visited[vecin]) {
                dfs(vecin, visited, topsort);
            }
        }

        topsort.push_back(i);
    }

    void print_output(vector<int> topsort) { 
        ofstream fout("sortaret.out");
        for (int i = 0; i < topsort.size() - 1; ++i) {
            fout << topsort[i] << " ";
        }
        fout << topsort[topsort.size() - 1] << "\n";
        fout.close();
    }

};

 

int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}