Cod sursa(job #2663516)

Utilizator rusuandrei32Rusu Andrei-Cristian rusuandrei32 Data 26 octombrie 2020 17:18:31
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

class Graph {
    int vertices;
    list <int> *adj;
public:
    Graph() {}

    Graph(int len) : vertices(len) {
        adj = new list<int>[len + 1];
    }

    void addEdge(int from, int to) {
        adj[from].push_back(to);
    }

    void depthFirst(int i, vector <bool> &visited, stack <int> &st) {
        visited[i] = true;

        for (auto &adjVal : adj[i]) {
            if (!visited[adjVal])
                depthFirst(adjVal, visited, st);
        }

        st.push(i);

    }
 
    void show(stack <int> &st) {
        while (true) {
            out << st.top();
            st.pop();
            if (!st.size())
                return;
            out << " ";
        }
    }
    
    void topologicalSort() {
        stack <int> st;
        vector <bool> visited(vertices, false);
        
        for (int i = 1; i <= vertices; ++i) {
            if (!visited[i])
                depthFirst(i, visited, st);
        }

        show(st);
    }
};

int main() {
    int N, M;
    in >> N >> M;
    Graph *myGraph = new Graph(N);

    while (M--) {
        int from, to;
        in >> from >> to;
        myGraph -> addEdge(from, to);
    }

    myGraph -> topologicalSort();

    return 0;
}