Cod sursa(job #1705474)

Utilizator elninoCristian elnino Data 20 mai 2016 17:28:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>

struct Node {
    int id;
    std::list<int> neighs;
    int exit_time;
    Node() : id(65535), exit_time(0) {}
};

int exittimeglob = 0;

bool sort_func (const Node &a, const Node &b) { return (a.exit_time > b.exit_time); }

void dfs(int N, int init_node, bool *visited, std::vector<Node> &graph) {
    std::stack<int> S;
    int curr_node;

    S.push(init_node);

    while(!S.empty()) {
        curr_node = S.top(); S.pop();

        if (!visited[curr_node]) {
            visited[curr_node] = true;
            for (std::list<int>::iterator neigh = graph[curr_node].neighs.begin();
                 neigh != graph[curr_node].neighs.end(); neigh++) {
                if (!visited[*neigh]) { S.push(*neigh); };
            }
        }

        graph[curr_node].exit_time = exittimeglob++;
    }
}

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

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

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

    // Citire Graph
    input >> N >> M;

    std::vector<Node> graph(N + 1);

    while(input >> u >> v) {
        graph[u].neighs.push_back(v);
        graph[u].id = u;
        graph[v].id = v;
    }

    bool visited[N + 1];
    std::memset(visited, 0, N + 1);

    // DFS
    for (int i = 1; i <= N; i++)
        if (!visited[i])
            dfs(N, 1, visited, graph);

    std::sort(graph.begin() + 1, graph.end(), sort_func);

    for (int i = 1; i <= N; i++) {
        if (graph[i].id > N) continue;
        output << graph[i].id << " ";
    }

    output << std::endl;

    input.close();
    output.close();

    return 0;
}