Cod sursa(job #2422833)

Utilizator melutMelut Zaid melut Data 20 mai 2019 04:38:32
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#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) {
    unsigned n;
    unsigned m;

    Read >> n;
    Read >> m;

    nodes.resize(n);

    unsigned node1;
    unsigned node2;

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

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


void DFS(vector<vector<ushort>> const &nodes, vector<ushort> &path, unsigned const node) {
    static bitset<MAX_N> visited;

    path.push_back(node);
    visited.set(node);

    for (ushort i = 0; i < nodes[node].size(); ++i) {
        DFS(nodes, path, nodes[node][i]);
    }
}


void PrintPath(vector<ushort> const &path) {
    for (unsigned i = 0; i < path.size(); ++i) {
        Write << path[i] + 1 << ' ';
    }
}


int main() {
    vector<vector<ushort>> nodes;
    vector<ushort> path;

    ReadArcs(nodes);

    DFS(nodes, path, 0);

    PrintPath(path);

    CloseFiles(Read, Write);

    return 0;
}