Cod sursa(job #1115754)

Utilizator nicu701Nicu Badescu nicu701 Data 22 februarie 2014 00:04:16
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

class TopSort {
private:
    stack<int> q;
    vector< pair<int, int> > edges;
    vector< vector<int> > adj_list;
    int no_vertices, no_edges, *visited;
    ifstream in;
    ofstream out;







public:
    TopSort() {
        in.open("sortaret.in");
        out.open("sortaret.out");
    }

    ~TopSort() {
        in.close();
        out.close();
        if (NULL != visited) {
            delete[] visited;
        }
    }

    void read_graph() {
        in >> no_vertices >> no_edges;
        adj_list.resize(no_vertices + 1);
        visited = new int[no_vertices + 1];

        for (int i = 1; i <= no_vertices; i++)
            visited[i] = 0;

        int left, right;
        for (int i = 0; i < no_edges; i++) {
            in >> left >> right;
            edges.push_back(pair<int, int>(left, right));
            adj_list[left].push_back(right);
        }
    }

    int find_unvisited() {
        for (int i = 1; i <= no_vertices; i++) {
            if (visited[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    void top_sort(int start_vertex) {
        if (visited[start_vertex] == 0) {
            visited[start_vertex] = 1;
            for (unsigned int i = 0; i < adj_list[start_vertex].size(); i++) {
                top_sort(adj_list[start_vertex][i]);
            }
            q.push(start_vertex);
        }
    }

    void solve() {
        int vertex;
        while ((vertex = find_unvisited()) != -1) {
            top_sort(vertex);
        }

        while (!q.empty()) {
            out << q.top() << " ";
            q.pop();
        }
    }
};


int main() {
    TopSort prob;
    prob.read_graph();
    prob.solve();
    return 0;
}