Cod sursa(job #2422841)

Utilizator melutMelut Zaid melut Data 20 mai 2019 07:13:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <string>
#include <vector>
#include <bitset>

using namespace std;


typedef unsigned short ushort;


string const inFile = "sortaret.in";
string const outFile = "sortaret.out";

ushort const MAX_N = 50 * 1000;


ifstream Read(inFile);
ofstream Write(outFile);


void CloseFiles(ifstream &Read, ofstream &Write) {
    Read.close();
    Write.close();
}


void ReadArcs(vector<vector<ushort>> &nodes) {
    ushort n;
    unsigned m;

    Read >> n;
    Read >> m;

    nodes.resize(n);

    ushort node1;
    ushort node2;

    while (m--) {
        Read >> node1;
        Read >> node2;

        nodes[node1 - 1].push_back(node2 - 1);
    }
}


inline void DFS(
    vector<vector<ushort>> const &nodes,
    bitset<MAX_N> &visited,
    vector<ushort> &order,
    ushort const node)
{
    visited.set(node);

    for (unsigned i = 0; i < nodes[node].size(); ++i) {
        if (visited[nodes[node][i]] == true) {
            continue;
        }

        DFS(nodes, visited, order, nodes[node][i]);
    }

    order.push_back(node);
}


void PrintOrder(vector<ushort> const &order) {
    for (int i = order.size() - 1; i >= 0; --i) {
        Write << order[i] + 1 << ' ';
    }
}


int main() {
    vector<vector<ushort>> nodes;
    bitset<MAX_N> visited;
    vector<ushort> order;

    ReadArcs(nodes);

    for (ushort i = 0; i < nodes.size(); ++i) {
        if (visited[i] == true) {
            continue;
        }

        DFS(nodes, visited, order, i);
    }

    PrintOrder(order);

    CloseFiles(Read, Write);

    return 0;
}