Cod sursa(job #1114754)

Utilizator nicu701Nicu Badescu nicu701 Data 21 februarie 2014 19:31:59
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <stack>


using namespace std;

class TopSort {
private:
    stack<int> q;
    vector< pair<int, int> > edges;
    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;
        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));
        }
    }

    vector<int> adjacent(int vertex) {
        vector<int> result;
        vector< pair<int, int> >::iterator it;
        for (it = edges.begin(); it != edges.end(); it++) {
            if (it->first == vertex) {
                result.push_back(it->second);
            }
        }
        return result;
    }

    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;
            vector<int> adj = adjacent(start_vertex);
            for (int i = 0; i < adj.size(); i++) {
                top_sort(adj[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;
}