Cod sursa(job #1989143)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 5 iunie 2017 23:43:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

void visit(int node, std::vector<int> *arr, int *check, std::list<int> &out) {
    if (check[node] == 1) {
        //fail
    }

    if (check[node] == 2) {
        return;
    }

    check[node] = 1;

    for (auto it = arr[node].begin(); it != arr[node].end(); it++) {
        visit(*it, arr, check, out);
    }

    check[node] = 2;

    out.push_front(node);
}

int main() {
    std::ifstream inFile("sortaret.in");
    std::ofstream outFile("sortaret.out");

    int nV, nM;

    inFile >> nV >> nM;

    std::vector<int> *arr = new std::vector<int>[nV + 1];

    int *check = new int[nV + 1];

    for (int i(0); i <= nV; i++) {
        check[i] = 0;
    }

    int a, b;
    for (int i(0); i < nM; i++) {
        inFile >> a >> b;
        arr[a].push_back(b);
    }

    std::list<int> out;

    for (int i(1); i <= nV; i++) {
        if (!check[i]) {
            visit(i, arr, check, out);
        }
    }

    while (!out.empty()) {
        outFile << out.front() << ' ';
        out.pop_front();
    }

    inFile.close();
    outFile.close();

    delete[] arr;
    delete[] check;

    return 0;
}