Cod sursa(job #1705513)

Utilizator elninoCristian elnino Data 20 mai 2016 18:39:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <list>

typedef std::list<int> List;

class Graph
{
    int nodes;
    List *adjList, *topsort_res;
    void visit(int root, bool *visited);

public:
    Graph(int nodes);
    ~Graph();
    void insert(int u, int v);
    List *topsort();
};

Graph::Graph(int nodes) {
    this->nodes = nodes;
    adjList = new List[nodes];
    topsort_res = NULL;
}

Graph::~Graph() {
    if (topsort_res) delete topsort_res;
}

inline void Graph::insert(int u, int v) {
    adjList[u].push_back(v);
}

void Graph::visit(int root, bool *visited) {

    visited[root] = true;

    for (List::iterator neigh = adjList[root].begin();
         neigh != adjList[root].end(); neigh++)
        if (!visited[*neigh]) visit(*neigh, visited);

    topsort_res->push_front(root);
}

List *Graph::topsort() {

    bool *visited = new bool[nodes];
    std::memset(visited, false, nodes);

    topsort_res = new List();

    // Sortare topologica
    for (int node = 0; node < nodes; node++)
      if (!visited[node])
        visit(node, visited);

    delete[] visited;

    return topsort_res;
}

int main(int argc, char **argv) {

    std::ifstream input("sortaret.in");
    std::ofstream output("sortaret.out");
    Graph *graph;
    int N, M, u, v;

    if (!input.is_open() || !output.is_open()) {
        std::cerr << "Cannot open input/output file!" << std::endl;
        return -1;
    }

    input >> N >> M;

    graph = new Graph(N);

    while(input >> u >> v)
        graph->insert(u - 1, v - 1);

    List *result = graph->topsort();

    for (List::iterator it = result->begin(); it != result->end(); it++)
        output << (*it + 1) << " ";

    delete graph;

    return 0;
}